10564 - Paths through the Hourglass
Moderator: Board moderators
The memory info is not always correct. If the program executes fast enough, it will always say your program used 64k even though that's not the case (my solution uses ~3 MB memory and is currently the first one on the ranklist). As for speed, I use memoization (not DP) + build the way on the fly. Memoization is probably better than DP because the big array can be quite sparse.
a late reply..
I got this program ac..
and it took 0.619 to get AC( not that bad) .
I would like to know whether everyone used methods similar to mine..
I actually turned over the hourglass and then applied dp..
.. otherwise it becomes very difficult to find the smallest string..
.. is this the method that everyone used.![:-?](./images/smilies/icon_confused.gif)
and it took 0.619 to get AC( not that bad) .
I would like to know whether everyone used methods similar to mine..
I actually turned over the hourglass and then applied dp..
.. otherwise it becomes very difficult to find the smallest string..
.. is this the method that everyone used.
![:-?](./images/smilies/icon_confused.gif)
10564
Code: Select all
11 119
8 9 2 7 9 5 4 3 1 2 3
3 4 1 1 3 8 7 4 2 7
7 9 3 1 9 8 6 5 0
2 8 6 0 2 4 8 6
5 0 9 0 0 6 1
3 8 9 3 4 4
6 0 6 6 1
8 4 9 6
3 7 8
8 2
9
1 3
5 9 8
4 0 7 6
3 6 1 5 4
2 0 9 7 3 7
2 6 0 1 6 5 7
5 4 1 2 0 0 1 4
6 0 7 1 7 7 7 7 3
3 5 9 9 8 1 8 2 6 6
0 3 8 0 1 2 5 0 9 4 7
16 145
1 0 8 1 0 9 2 4 9 1 5 7 3 3 4 2
2 0 1 2 7 7 0 2 4 1 0 3 7 3 9
5 9 7 2 0 2 8 6 7 0 8 1 8 3
0 3 6 2 0 2 8 4 1 8 3 7 5
8 1 7 0 4 8 8 1 3 6 7 8
9 5 5 5 6 6 3 0 0 8 8
2 3 0 6 5 0 9 7 2 2
8 2 9 4 4 8 2 7 2
5 8 4 7 3 9 5 1
9 0 2 8 3 1 4
3 1 0 4 0 7
9 0 8 1 4
0 7 9 5
3 8 2
3 2
1
0 4
0 7 5
9 0 5 1
2 0 9 8 9
1 7 3 3 0 7
6 6 0 2 8 9 8
9 9 9 4 2 0 8 7
8 7 3 0 7 6 4 2 1
9 1 6 0 3 3 6 2 2 1
4 3 2 6 0 5 4 9 6 0 8
2 7 4 0 7 6 0 1 2 9 3 8
5 1 5 6 6 8 8 9 8 7 0 7 9
1 5 8 6 3 9 4 5 3 8 2 3 9 4
8 5 1 3 2 8 1 6 4 6 7 7 9 6 4
1 9 2 6 3 1 5 9 7 0 2 6 1 7 6 2
19 272
3 0 2 7 7 7 0 2 0 0 8 6 4 5 0 1 5 7 3
2 7 9 1 1 4 0 3 3 1 5 8 3 0 5 1 0 2
5 1 0 4 0 6 4 8 9 5 6 2 2 2 1 7 4
7 8 6 0 0 2 1 3 9 2 4 1 5 4 0 6
6 8 1 3 3 1 0 5 8 9 3 8 9 8 4
3 9 9 6 9 7 7 2 5 2 3 2 8 3
3 8 5 7 8 8 1 3 5 1 2 0 8
6 5 5 3 9 5 3 5 4 8 5 0
3 5 0 8 4 3 5 8 1 2 6
0 2 2 1 6 5 0 1 7 7
3 8 3 5 1 3 2 1 9
4 2 3 0 1 4 8 6
6 1 3 8 7 9 4
4 3 5 4 4 2
7 7 5 6 6
9 0 7 0
9 8 6
7 3
2
0 1
5 3 5
6 5 4 6
8 1 5 8 5
3 3 2 8 7 6
9 6 4 6 3 2 1
0 5 8 7 0 0 3 7
3 4 6 2 0 1 1 6 5
3 4 9 5 3 4 3 7 7 0
9 1 5 4 0 0 7 1 2 3 7
7 3 3 3 9 1 5 8 8 8 0 2
4 4 3 3 6 7 6 6 1 4 8 1 6
5 9 6 8 7 1 9 1 6 7 6 3 7 1
2 7 9 4 7 1 8 2 4 8 8 1 6 2 0
4 8 5 9 4 4 4 9 9 4 5 3 2 1 7 4
3 1 9 0 7 3 8 4 2 6 9 8 7 7 4 8 7
8 3 2 1 9 3 7 4 4 4 3 5 1 3 2 8 0 9
0 3 4 9 4 4 3 9 8 5 3 8 1 2 3 8 9 8 5
20 240
6 1 8 1 8 7 7 2 8 2 3 6 6 9 6 5 1 3 8 0
7 6 1 6 0 3 1 0 4 3 1 5 8 9 5 4 5 7 4
4 6 7 7 5 2 6 8 8 9 1 9 8 0 5 0 2 9
6 0 2 2 9 2 6 7 3 6 0 5 2 1 7 1 1
5 3 2 6 6 8 1 5 8 6 9 4 6 6 2 8
8 1 6 8 7 8 9 7 9 0 5 8 2 6 9
7 1 7 5 1 6 4 4 9 9 6 1 5 5
6 0 7 5 0 7 9 5 6 8 5 3 7
0 7 5 2 3 0 4 9 8 5 8 0
0 9 7 7 4 4 7 5 9 2 3
2 2 3 1 9 7 3 0 4 3
7 8 0 8 8 1 2 7 4
9 1 9 3 6 2 0 7
2 0 0 5 3 5 7
7 4 4 3 3 8
6 4 4 5 9
2 4 4 2
4 2 5
3 2
3
4 0
2 3 7
2 0 7 7
6 1 7 5 6
7 9 0 8 5 7
4 2 5 6 5 8 8
2 8 5 2 7 6 7 3
3 5 6 9 4 4 5 9 6
9 2 9 5 6 1 7 8 3 7
2 6 9 1 0 0 4 5 6 3 6
4 6 7 6 3 9 1 4 7 5 0 0
5 5 8 8 6 9 8 1 5 6 0 6 0
4 7 8 6 4 0 3 4 1 0 0 4 3 6
1 0 5 6 8 6 7 6 7 8 9 4 5 1 0
2 8 6 7 0 7 7 4 6 2 2 9 6 5 6 4
0 6 9 6 2 9 1 2 6 4 7 0 8 2 4 1 0
0 3 6 1 7 9 8 0 2 9 8 9 7 4 7 7 5 3
9 1 2 9 6 1 1 4 9 8 6 9 7 4 8 2 5 8 2
5 6 1 9 3 7 1 3 2 0 6 8 9 9 3 9 1 1 3 4
3 42
4 9 1
4 3
9
4 9
5 2 1
12 149
2 5 1 8 0 7 5 7 4 2 9 1
8 4 4 8 1 2 8 4 6 7 3
1 5 8 5 4 2 6 6 4 6
1 4 0 4 6 6 7 5 8
1 1 5 1 1 9 0 7
6 3 4 4 5 7 2
6 5 6 2 9 6
5 3 2 1 6
3 4 9 0
5 6 5
0 6
5
3 3
2 6 6
0 6 2 0
0 5 2 0 5
6 1 0 4 9 4
0 2 6 6 4 0 7
2 6 6 8 5 1 0 0
2 1 3 8 4 3 5 0 8
7 0 5 3 5 6 3 0 2 9
9 3 7 9 3 9 3 0 2 5 1
1 8 3 3 7 4 6 7 1 9 4 6
20 242
8 2 5 7 7 8 4 2 0 6 5 0 5 6 0 7 2 4 4 4
0 5 0 6 6 2 6 3 1 7 5 5 5 4 8 9 9 8 1
2 7 7 9 2 1 8 2 9 7 9 9 0 0 6 4 2 5
3 5 1 9 7 8 4 9 1 9 8 7 9 6 9 5 6
4 7 4 4 8 6 5 1 4 9 8 8 7 3 4 5
7 7 5 1 3 3 7 9 6 5 3 4 0 2 4
9 8 0 4 2 6 1 5 6 1 0 5 0 4
8 7 0 8 1 7 2 8 0 1 1 9 1
0 3 2 3 2 2 8 1 8 7 5 6
2 6 4 7 4 3 7 0 5 4 3
7 3 8 0 5 6 8 2 6 8
1 2 6 6 2 4 3 0 2
0 5 1 0 5 8 0 1
3 8 2 8 4 5 7
2 3 8 9 1 6
2 2 1 3 8
5 6 6 8
9 3 5
7 6
9
5 7
7 0 0
2 5 9 3
0 3 7 6 1
5 2 5 9 5 3
5 5 3 6 6 8 5
2 1 0 2 6 8 9 6
2 5 8 8 6 6 1 6 7
1 2 5 2 4 9 2 7 0 0
4 9 0 8 1 0 0 1 7 3 5
6 9 5 0 6 6 2 3 6 7 5 2
5 6 6 6 7 8 6 4 5 5 8 0 0
4 4 2 2 8 6 5 0 9 9 9 3 8 7
1 5 1 9 9 8 5 2 3 1 0 7 3 8 8
5 9 6 9 3 1 1 9 1 2 4 6 8 0 8 9
5 0 4 6 8 6 7 3 3 1 7 3 1 3 4 2 7
7 3 3 6 5 5 3 6 0 9 5 6 3 3 2 9 9 6
3 5 5 1 4 7 1 7 9 9 6 5 2 2 3 7 0 9 7
6 9 5 6 9 9 3 5 8 1 8 9 6 1 8 4 5 3 4 6
16 271
5 2 1 7 5 4 8 3 8 5 2 3 1 3 2 0
0 0 8 5 2 8 8 7 1 0 8 6 3 2 2
2 7 0 8 4 7 4 3 4 4 4 6 0 5
5 3 7 2 1 9 0 8 8 8 0 9 1
6 7 8 6 5 9 8 0 5 4 6 7
6 4 0 1 8 8 4 9 4 6 4
0 9 2 9 1 2 4 3 9 9
7 7 6 6 7 9 3 9 4
5 4 6 9 8 6 8 2
6 7 5 8 6 8 2
4 3 5 6 6 2
6 4 9 2 4
2 9 6 6
2 2 5
6 5
2
9 5
7 4 4
3 4 9 2
1 3 3 7 3
3 0 5 4 5 1
2 8 5 6 0 1 8
9 2 7 3 8 4 2 6
7 6 3 0 2 9 3 9 9
2 2 2 9 4 9 4 8 4 6
3 4 2 8 3 3 7 8 3 7 5
9 1 4 9 1 7 6 2 5 2 2 8
6 1 5 5 9 6 2 6 8 9 0 6 4
0 6 6 3 5 4 1 8 8 4 4 7 3 2
4 3 2 5 1 2 4 9 5 0 6 8 5 4 1
9 1 9 2 3 2 2 2 9 1 7 5 0 9 9 8
6 60
0 1 8 0 6 8
4 5 5 0 8
6 0 5 4
6 2 9
3 2
5
6 3
5 7 2
8 5 4 8
9 2 8 6 8
8 8 5 9 9 4
4 37
9 8 7 8
3 1 3
0 6
6
3 4
0 8 3
7 6 6 0
7 70
0 7 3 6 8 7 9
4 8 0 8 5 7
2 4 2 9 2
0 1 5 0
1 4 0
0 5
7
4 7
7 5 2
8 3 5 9
7 8 9 6 0
9 0 1 9 1 6
0 1 4 3 4 7 9
14 181
0 7 5 5 4 9 4 2 0 9 7 3 3 7
7 0 5 3 1 2 6 4 2 4 6 0 3
5 2 7 1 1 4 9 6 5 9 8 7
8 4 0 2 9 0 5 8 2 6 2
9 6 9 8 3 9 5 7 0 1
2 0 7 6 5 6 3 2 8
5 5 8 8 0 1 9 4
5 6 7 7 1 8 3
6 3 3 8 3 5
9 6 1 1 9
4 3 9 1
9 2 6
0 7
0
9 3
8 7 3
0 8 6 8
3 0 6 8 5
3 9 8 6 0 5
6 3 8 9 6 0 5
9 9 1 7 5 4 8 8
4 1 1 7 0 2 5 6 8
8 0 5 3 4 3 7 5 6 0
6 1 0 9 8 7 9 5 3 7 1
1 7 3 1 6 9 1 4 2 7 0 8
6 4 9 7 0 1 3 1 1 9 9 9 5
9 3 5 6 1 4 3 9 5 4 5 5 0 3
10 132
2 4 3 0 5 8 0 3 0 6
5 4 0 8 8 4 8 1 7
7 8 0 9 0 0 0 2
0 4 5 4 2 1 6
8 4 6 6 6 2
8 8 5 2 7
6 9 2 1
6 0 7
6 0
0
5 5
8 4 4
3 9 6 3
6 8 4 1 1
5 5 4 2 9 2
4 0 5 7 6 0 4
4 7 5 5 9 1 8 4
4 6 5 1 0 4 9 9 5
8 7 5 4 8 6 0 2 6 2
7 112
1 5 9 5 9 8 9
7 4 0 8 4 7
2 0 8 8 6
0 2 3 9
1 3 7
9 3
3
1 2
5 6 2
0 6 1 7
7 0 5 6 1
2 2 6 1 0 5
5 3 3 1 2 5 7
11 139
7 1 2 2 8 0 9 4 9 3 1
4 1 4 3 0 4 8 7 3 2
8 2 3 9 8 5 0 8 3
5 1 5 8 3 7 1 6
0 9 0 5 3 1 4
2 0 1 5 9 0
4 2 6 0 5
2 4 2 3
8 5 0
5 3
2
9 7
3 7 4
9 8 8 8
0 9 7 3 0
7 6 1 2 4 2
8 6 3 9 8 3 5
1 0 9 6 2 5 4 8
5 3 1 7 0 8 0 4 6
9 6 8 5 2 2 2 1 7 8
5 9 9 2 9 6 9 5 0 6 2
16 270
3 1 6 1 0 2 2 1 0 3 5 5 0 0 8 0
1 6 4 4 9 0 9 2 5 1 4 0 2 1 5
1 6 3 0 8 2 5 6 4 2 4 5 2 1
1 5 0 5 1 7 2 3 7 3 0 9 8
4 4 9 5 0 5 1 2 4 0 6 0
1 9 9 3 7 0 5 6 0 8 5
7 9 1 0 2 6 9 0 9 5
9 9 1 1 4 7 5 1 3
9 8 4 3 4 4 0 1
7 4 1 7 5 0 9
5 8 1 2 7 0
9 6 7 8 8
4 8 5 1
3 5 1
4 7
2
4 6
4 8 1
4 8 6 6
6 0 9 7 9
9 3 4 1 4 0
7 6 2 2 8 6 2
3 8 9 3 7 3 7 6
4 1 3 0 3 2 0 2 3
4 3 7 5 2 0 7 6 0 8
6 8 9 4 3 9 3 3 0 0 7
0 7 2 3 7 3 1 5 9 1 8 1
8 3 8 8 8 4 7 2 1 2 6 7 0
8 3 4 1 9 2 2 1 1 3 5 1 1 0
8 1 2 4 4 5 0 5 5 3 0 8 9 0 7
2 8 0 5 9 8 9 1 1 5 3 7 9 0 7 4
11 149
2 1 4 6 2 7 1 1 2 5 8
5 8 4 6 8 5 8 5 9 7
2 1 9 7 2 3 5 2 7
9 6 5 2 8 3 5 7
3 5 9 7 9 1 0
3 8 2 8 6 1
5 6 9 1 8
9 2 9 8
8 4 2
8 6
1
7 3
1 4 9
7 5 9 8
1 5 5 2 2
6 7 3 7 9 4
7 2 4 9 3 7 4
2 1 9 6 7 9 9 4
6 2 7 7 3 1 2 9 7
1 2 6 6 3 7 4 2 2 5
6 4 1 5 3 2 3 2 9 2 9
18 215
5 9 4 2 9 0 2 5 3 1 9 0 4 7 5 9 0 8
8 2 8 5 4 4 1 4 7 5 9 1 4 9 0 6 0
7 3 1 1 8 6 0 3 1 6 8 4 1 5 2 6
0 4 3 0 6 9 5 6 3 5 2 8 5 0 6
5 6 4 2 2 5 5 6 1 3 6 0 3 0
1 4 3 7 0 9 2 5 2 2 8 4 2
8 5 8 2 7 2 2 0 3 9 1 0
1 5 4 4 5 9 9 2 6 9 0
3 5 6 8 8 9 5 6 9 1
4 2 0 7 8 7 8 1 8
3 3 5 1 7 2 5 1
5 8 2 4 0 8 1
5 3 3 5 8 5
7 9 9 2 4
4 1 6 9
2 6 8
5 2
0
1 2
8 2 9
7 6 8 8
7 8 5 4 5
9 1 0 0 6 1
8 7 1 7 1 0 7
7 9 3 6 0 3 4 4
9 6 5 9 8 0 3 8 6
4 3 1 4 3 1 2 0 7 4
8 4 9 3 9 7 1 5 7 3 2
8 5 9 7 9 3 7 5 0 1 9 8
4 6 2 1 3 9 0 7 2 8 0 9 2
0 9 4 2 0 6 6 4 6 1 3 6 4 5
8 9 7 4 4 1 6 7 5 4 0 2 3 3 2
2 3 9 8 9 3 9 7 5 5 2 9 5 8 9 7
0 4 1 0 3 8 2 7 3 2 3 5 6 0 7 2 9
6 6 4 2 7 5 9 6 0 7 6 1 5 0 2 5 7 8
3 39
9 2 5
2 9
3
0 2
2 6 0
2 28
5 1
6
5 4
11 164
9 2 1 9 7 1 6 4 3 1 7
5 5 5 2 9 0 8 3 9 9
2 4 4 2 5 5 3 6 2
8 4 1 2 6 6 9 1
4 3 4 6 8 4 3
8 4 7 4 6 4
6 6 3 8 0
6 1 1 6
9 0 5
8 1
1
1 5
8 3 4
9 0 8 1
9 3 8 7 4
7 0 7 6 3 9
2 6 9 8 9 5 1
7 0 0 7 1 2 6 9
4 3 0 2 2 2 3 3 3
1 0 2 3 0 9 9 2 6 5
6 6 3 4 8 8 8 8 3 5 1
15 167
3 7 4 0 6 1 9 4 6 2 4 3 0 1 3
5 8 3 7 4 7 1 2 3 9 0 8 2 8
6 0 7 8 1 6 5 1 4 0 5 7 9
0 5 3 9 4 8 4 3 8 8 0 7
4 3 3 2 0 8 6 4 6 9 7
7 7 9 2 5 5 6 7 6 4
5 0 6 2 5 3 6 6 8
6 3 4 9 1 5 4 4
4 3 9 6 7 4 7
6 3 4 2 1 9
5 9 6 1 1
8 3 6 0
6 9 0
9 4
6
9 3
6 1 3
6 3 0 7
5 2 7 9 5
3 3 1 6 9 5
8 3 8 7 1 1 4
3 5 7 0 1 7 8 6
5 1 6 9 9 1 1 2 9
5 3 0 4 6 3 2 8 9 5
0 0 8 1 8 5 7 0 4 7 4
3 4 2 5 4 0 2 4 9 4 6 3
8 8 9 1 9 3 2 0 6 0 8 8 0
3 1 2 4 9 5 5 2 9 8 2 9 0 0
6 7 4 2 6 3 4 3 6 1 1 4 1 2 9
15 241
0 9 8 9 5 2 0 7 4 0 9 2 5 3 5
8 2 4 6 8 3 1 7 8 7 2 5 0 8
5 3 0 6 1 9 5 1 7 4 0 3 9
0 8 3 0 8 1 4 3 4 2 6 4
6 5 4 8 2 0 9 8 2 1 4
0 6 2 4 2 0 6 6 6 2
7 1 1 9 7 2 5 1 3
0 8 9 8 4 1 6 6
7 1 0 2 8 3 3
1 2 6 3 1 5
4 5 3 4 4
7 3 4 3
2 1 4
0 7
8
9 7
0 3 1
3 6 1 0
8 3 3 1 3
2 1 4 9 6 2
4 9 2 2 1 9 0
0 9 5 2 5 1 7 1
3 1 6 5 3 0 3 4 2
4 3 6 2 5 9 3 7 6 3
9 1 0 5 8 1 9 0 5 4 8
8 4 8 3 8 7 5 0 2 5 0 1
5 2 4 6 2 4 5 5 4 9 4 9 2
9 6 9 1 3 0 6 2 3 3 9 0 5 7
0 9 9 0 1 7 9 3 4 1 5 5 3 4 9
10 145
4 8 1 3 6 3 7 1 5 1
1 0 2 5 0 1 0 7 3
4 3 1 1 8 7 9 0
5 9 2 1 2 0 3
4 7 0 0 1 8
3 1 1 8 8
3 3 5 9
2 8 3
4 5
9
0 6
2 4 5
9 8 5 1
8 7 6 7 5
9 4 3 1 0 5
4 6 0 8 1 1 7
4 4 5 4 2 9 0 7
9 4 7 0 5 6 4 9 2
5 5 1 2 1 4 3 3 2 1
14 208
9 3 5 5 0 6 1 7 3 1 6 2 0 4
6 8 2 9 6 8 1 9 6 3 9 8 7
5 3 0 0 5 4 1 3 5 7 3 7
8 4 2 8 0 4 1 6 5 8 3
7 2 1 9 7 1 2 1 1 2
1 3 5 6 0 1 5 3 0
8 5 3 2 2 6 7 9
2 9 6 1 2 1 0
0 8 0 0 5 9
8 1 2 4 3
0 2 0 0
4 1 9
6 5
3
9 7
4 8 9
4 0 8 7
7 5 6 0 3
8 0 9 4 9 3
5 4 7 8 6 1 4
7 3 9 7 0 5 4 4
6 5 8 4 7 8 7 5 2
1 7 7 6 9 4 9 3 1 1
4 9 5 5 0 2 3 9 6 9 8
8 1 3 6 0 0 9 5 4 8 7 4
9 9 8 3 8 5 2 1 5 3 1 6 7
3 0 5 2 2 1 5 0 2 6 2 8 3 6
12 172
5 3 7 7 8 8 4 0 3 5 8 9
3 1 7 0 9 3 3 5 7 3 6
4 9 4 0 0 9 7 8 6 5
2 2 3 5 3 7 9 1 0
5 0 9 3 6 5 5 9
6 1 9 9 1 7 5
9 4 7 5 0 3
2 0 3 8 8
5 9 4 0
3 7 7
9 5
9
0 6
8 7 6
9 0 9 1
7 9 8 5 9
0 4 0 5 2 5
8 0 7 4 9 3 4
0 1 1 4 7 1 0 6
4 3 8 0 1 0 4 5 3
5 9 4 2 7 0 8 2 3 0
1 2 5 7 5 1 8 5 3 1 6
0 8 4 8 7 5 7 5 5 0 2 4
15 175
4 9 5 4 1 2 4 7 9 0 2 2 4 7 7
0 1 7 1 7 8 5 1 5 7 4 3 7 2
9 2 2 5 2 5 0 4 0 8 8 4 4
3 3 5 2 2 0 5 0 4 3 2 6
8 8 1 5 6 2 3 8 9 1 1
5 6 8 1 8 7 1 9 9 2
0 4 1 2 8 0 0 4 6
0 0 3 9 8 5 4 5
4 4 8 0 9 8 9
7 0 9 8 4 9
2 0 8 0 7
3 0 2 5
0 7 0
2 7
9
0 0
6 4 1
5 1 2 9
7 0 6 3 6
3 6 7 6 6 3
3 2 4 8 1 7 1
9 0 6 7 1 3 3 8
1 7 9 1 3 0 1 8 3
0 3 4 6 7 3 2 5 4 8
2 7 9 3 6 5 4 6 4 1 9
8 7 6 0 1 3 5 5 6 8 6 8
2 4 6 5 3 3 9 4 8 9 2 0 1
5 5 9 4 7 5 0 9 0 1 4 1 3 2
9 8 6 3 9 9 5 1 1 0 7 6 9 2 2
2 28
9 3
2
3 4
15 203
0 1 6 8 9 5 7 6 3 8 2 1 4 5 4
0 9 1 1 8 5 5 5 4 3 0 9 7 7
9 1 1 9 8 4 7 9 2 5 9 9 4
7 6 8 7 4 9 6 2 3 6 7 1
8 8 1 3 4 8 4 8 8 5 4
4 1 0 1 2 1 0 2 0 5
0 1 0 8 7 0 5 2 5
4 2 4 2 9 8 5 6
6 1 0 4 1 6 6
5 3 1 4 6 2
9 1 6 7 7
7 7 0 5
7 7 0
3 3
7
3 1
5 1 7
8 0 4 1
9 3 0 8 0
8 2 1 0 6 3
8 5 4 9 4 1 5
8 0 8 5 8 1 1 5
1 6 2 9 1 7 0 5 4
2 7 6 8 2 7 9 5 8 1
8 3 7 9 3 5 8 3 0 9 5
6 9 3 8 9 8 1 7 3 6 8 6
3 2 6 0 8 7 0 4 8 1 8 1 3
8 7 8 9 5 1 9 6 6 9 5 5 2 8
1 6 2 7 8 8 0 5 0 9 9 7 3 3 6
4 55
8 3 9 2
6 6 5
9 1
4
9 8
7 4 4
2 7 2 7
17 277
9 8 1 6 2 2 7 4 8 3 9 8 4 6 8 6 8
7 5 8 7 5 7 1 7 3 7 0 9 6 9 2 2
0 1 6 1 5 5 9 6 4 6 7 2 6 8 6
9 2 8 8 4 4 0 7 9 9 8 4 1 1
5 6 7 3 2 0 8 8 9 3 1 3 6
1 0 1 5 2 2 2 0 4 2 7 1
8 3 3 4 9 6 3 3 2 2 6
5 2 2 4 5 6 2 3 8 5
7 8 1 1 0 0 0 3 7
9 6 7 8 8 7 1 5
2 3 1 6 6 4 2
1 9 7 2 8 2
8 2 6 0 7
9 4 1 8
6 1 0
7 8
9
5 1
8 4 1
6 4 7 5
7 9 3 0 4
4 9 5 0 7 4
9 6 4 7 5 5 8
5 0 2 1 7 0 2 1
8 1 2 6 6 0 8 1 1
8 2 8 0 8 8 5 2 8 0
3 7 3 5 4 3 2 5 4 5 1
8 8 4 0 1 8 2 9 7 6 2 2
4 1 7 4 2 1 4 2 9 4 7 0 3
1 6 1 7 7 2 5 3 7 7 9 1 3 8
2 4 7 2 2 2 7 4 1 8 8 1 7 3 2
1 0 9 1 5 7 8 9 1 7 3 7 8 7 4 6
5 2 1 9 9 9 7 2 6 0 2 5 1 0 0 1 0
11 156
4 1 5 0 9 5 2 4 3 0 0
1 6 8 7 1 7 0 2 7 7
6 4 5 9 6 0 5 5 8
5 4 3 3 6 3 7 6
2 7 9 6 7 5 0
8 5 0 7 3 6
6 2 5 1 7
0 3 7 2
5 4 5
4 6
0
6 7
5 7 8
8 1 6 9
2 2 3 8 2
1 1 6 4 7 8
6 8 2 3 7 1 1
9 7 0 7 9 0 4 0
7 7 9 6 9 8 1 8 2
1 7 3 3 6 9 3 1 6 4
8 8 5 1 1 0 3 6 9 6 9
17 259
9 5 4 8 4 2 6 8 6 3 3 1 6 0 6 9 2
0 3 3 6 6 6 4 8 6 0 0 6 9 8 7 8
4 9 7 8 0 1 1 0 3 4 9 7 0 3 2
7 0 5 2 2 9 0 1 5 5 6 7 3 9
6 8 5 9 6 6 0 3 6 2 1 3 8
7 5 9 9 7 5 2 2 7 0 3 5
5 2 6 5 2 7 0 9 5 5 7
7 7 3 6 5 5 6 1 3 5
3 0 6 1 7 3 8 4 3
4 6 4 8 5 2 5 1
6 3 0 4 4 7 2
4 6 1 6 6 6
3 3 1 6 5
5 6 8 8
9 1 4
7 0
4
5 5
5 4 7
5 2 9 8
0 2 6 5 2
5 8 9 9 8 6
3 0 0 1 3 8 6
8 8 2 5 9 7 1 4
2 0 9 8 1 7 6 5 6
5 3 3 5 6 3 5 5 7 0
1 0 3 7 3 1 3 4 9 6 0
2 1 9 8 8 8 7 5 0 9 0 3
7 2 5 2 3 5 7 7 9 0 1 1 4
4 5 9 5 6 4 7 6 8 0 0 0 8 6
7 8 3 3 8 2 6 3 8 5 6 7 0 6 1
1 3 9 5 0 1 3 8 8 6 7 9 7 0 6 0
1 4 6 4 2 8 2 2 6 8 7 9 2 9 3 8 6
7 107
6 8 8 6 7 3 3
1 1 5 0 4 0
3 4 4 4 2
4 9 1 3
7 1 2
3 8
1
4 1
5 0 2
6 6 0 7
3 7 2 0 0
8 5 9 9 1 9
5 6 9 3 9 3 4
5 55
6 5 2 6 7
2 4 8 8
2 8 0
7 7
1
6 6
6 7 4
0 7 5 1
3 3 9 6 2
18 312
7 0 6 3 7 3 0 0 5 9 1 1 2 2 2 0 5 1
8 8 1 2 7 5 5 0 1 2 0 8 7 2 0 9 7
3 0 6 2 3 9 2 9 3 3 3 4 6 6 5 4
0 2 2 5 3 9 5 7 8 9 4 6 3 4 2
0 5 6 9 8 5 2 8 9 9 2 3 7 0
6 3 0 1 6 7 5 6 3 9 0 6 3
6 5 7 1 1 1 0 6 3 8 8 7
4 8 9 0 9 5 6 5 2 4 8
7 0 8 3 8 7 1 8 2 7
5 6 0 2 4 2 7 6 3
6 8 6 4 5 3 0 8
6 9 8 8 2 1 6
3 2 6 0 6 2
8 8 6 2 6
1 3 4 8
7 2 5
1 5
7
1 7
4 8 0
4 6 4 1
5 6 4 5 6
5 0 4 9 2 1
7 7 7 7 6 3 5
2 1 7 9 6 1 5 6
9 6 1 8 0 4 7 5 7
3 5 7 4 0 5 8 4 3 1
6 3 8 0 1 0 3 3 9 2 3
7 8 9 3 7 0 3 7 1 3 3 0
4 9 8 3 8 7 0 8 4 2 8 6 4
8 6 7 5 7 7 1 5 0 0 5 8 9 8
2 8 7 6 3 5 8 0 1 0 7 2 9 3 8
6 0 7 3 6 0 8 6 6 0 9 9 3 2 8 0
7 5 5 2 6 0 9 5 0 7 4 5 5 6 0 8 9
0 3 7 7 3 5 3 4 6 4 2 5 1 5 1 5 4 8
6 83
0 5 6 5 0 9
7 5 7 9 3
4 8 3 8
6 0 7
9 6
5
5 7
3 6 0
3 3 9 9
3 0 1 1 8
3 8 8 2 0 8
3 52
0 8 5
1 5
9
6 3
6 9 4
7 123
9 7 8 1 5 2 3
0 7 5 4 4 5
3 2 0 7 7
5 2 6 6
0 1 4
1 1
8
6 5
6 9 4
6 2 2 2
1 0 5 0 8
9 7 7 8 2 1
4 3 8 0 7 8 7
16 287
0 0 6 0 8 1 0 6 0 4 8 7 3 5 9 7
8 6 4 8 6 5 3 3 1 8 6 3 9 7 3
1 7 5 2 5 0 2 1 5 0 3 8 7 5
3 2 4 9 0 8 5 3 3 7 5 0 5
0 2 8 1 3 6 3 1 8 6 0 9
7 7 2 8 9 2 3 8 9 8 6
0 2 5 7 7 4 4 2 2 6
4 5 4 8 3 4 1 5 0
7 8 8 7 4 2 7 8
1 9 8 0 2 0 2
4 7 5 7 0 7
0 0 5 4 3
4 4 0 8
2 5 0
3 8
1
4 7
3 0 4
7 7 0 9
5 7 7 5 0
8 9 3 8 4 9
0 6 5 0 8 3 0
2 2 6 7 1 4 1 0
5 2 3 3 4 7 8 4 2
6 8 7 1 7 3 2 2 0 1
5 5 6 7 1 3 8 2 7 3 6
3 4 7 5 6 9 2 8 2 4 1 6
8 5 4 4 4 8 1 1 0 3 5 8 9
9 0 9 2 8 3 0 1 4 5 4 1 5 4
6 8 7 4 9 3 5 6 2 8 3 6 6 6 5
5 7 3 1 9 8 9 7 2 2 6 2 1 5 9 4
5 73
9 9 5 2 2
2 7 1 8
4 1 0
9 8
5
7 8
4 5 5
9 7 5 6
3 1 9 4 4
15 211
1 2 9 8 1 0 4 5 3 2 8 2 0 1 7
2 7 9 1 8 0 5 5 0 0 1 8 5 8
1 4 7 5 1 2 0 1 7 5 9 1 3
5 9 3 2 1 5 9 7 4 5 4 2
7 4 5 5 5 9 8 5 5 1 6
9 9 7 2 8 9 3 1 1 1
6 8 9 8 6 1 1 3 1
1 9 6 7 2 1 5 5
8 9 1 0 4 4 8
3 6 3 3 1 1
2 3 9 3 0
6 0 6 2
6 4 3
1 2
9
3 2
2 9 2
4 9 0 6
5 5 2 2 6
5 5 0 6 8 6
8 4 3 6 6 5 5
1 9 6 8 6 8 8 5
9 2 3 8 9 3 6 8 1
0 4 1 7 7 9 1 2 9 5
3 9 0 1 8 5 7 5 7 0 8
6 5 2 2 5 8 5 6 0 1 3 6
8 7 3 4 6 6 5 7 8 6 8 4 4
3 9 5 2 3 7 7 6 7 0 7 9 6 8
0 2 4 5 8 4 8 9 7 2 1 0 9 6 3
12 178
1 8 4 8 2 3 6 7 7 5 3 2
6 5 1 6 4 4 2 3 0 0 6
9 4 8 0 2 6 5 3 3 4
1 8 1 5 3 3 3 6 3
5 3 2 7 4 9 7 6
4 4 1 5 2 0 0
7 5 5 3 1 2
5 9 8 8 6
0 6 3 3
7 3 0
4 4
5
4 4
1 5 0
7 2 9 7
8 3 8 9 9
6 5 4 6 7 7
2 1 0 1 5 5 3
7 6 8 7 3 8 4 7
9 4 0 1 3 5 7 0 1
7 7 0 4 1 9 1 0 0 6
3 8 3 0 2 5 1 5 6 8 4
1 3 3 8 6 7 8 2 8 2 4 4
14 159
8 7 0 1 6 2 6 4 4 5 2 9 8 4
1 6 5 8 9 0 3 8 5 5 2 4 2
4 5 0 3 4 2 4 1 8 0 4 1
1 2 3 6 0 1 5 9 8 4 7
3 9 6 8 5 4 4 7 9 8
1 2 2 2 7 2 7 8 2
8 3 3 8 1 0 6 9
9 9 7 4 6 1 9
5 8 9 9 1 9
7 9 3 4 5
0 3 9 4
2 8 4
7 2
7
6 2
2 0 8
9 1 3 7
3 5 4 8 5
4 1 4 2 3 4
6 3 1 1 3 5 6
6 8 1 1 0 0 3 7
1 1 2 9 6 9 4 3 0
1 7 9 7 5 1 5 8 2 0
4 5 9 0 5 1 1 0 7 9 7
5 6 2 2 9 6 4 4 4 0 9 3
6 3 1 2 5 7 7 8 8 6 0 7 9
4 9 9 4 9 2 9 8 7 3 2 8 3 7
8 118
4 4 7 3 4 6 3 1
2 2 4 0 9 5 5
3 1 2 1 7 0
8 4 3 7 6
1 9 3 6
5 0 4
0 2
3
5 5
6 6 7
6 6 0 6
4 3 4 5 9
8 6 9 6 2 9
6 2 0 6 9 4 3
6 2 9 0 5 1 6 7
18 175
8 3 1 3 2 5 2 0 1 6 1 7 3 9 5 1 7 3
3 6 6 6 5 3 4 7 4 7 2 6 1 9 8 1 1
7 6 8 2 5 0 1 7 0 6 7 4 6 5 9 5
1 4 2 7 0 6 8 1 8 4 9 5 1 8 1
0 2 4 1 5 6 3 6 8 9 3 0 5 0
1 0 5 7 8 6 6 9 3 8 3 1 0
5 0 0 6 0 5 0 5 0 3 6 0
8 6 7 6 1 9 4 4 6 3 6
3 4 5 7 0 7 9 3 8 0
4 2 6 0 0 1 9 8 0
8 2 1 2 1 6 4 9
3 0 5 7 9 8 9
2 6 8 8 9 0
3 2 9 3 4
5 3 0 9
9 8 7
4 6
8
6 6
8 6 0
2 5 6 9
1 2 1 7 9
9 3 1 7 7 4
8 4 2 5 7 6 9
3 2 2 1 2 7 8 4
8 5 9 1 8 1 7 5 9
8 3 6 7 7 8 5 5 0 0
0 7 6 4 2 6 6 9 0 3 3
9 8 5 9 1 0 7 0 1 2 3 4
7 1 6 3 6 8 8 2 4 5 2 3 0
2 2 8 6 3 1 0 4 4 5 1 2 2 8
9 1 9 9 8 4 4 7 8 6 8 8 3 9 4
0 9 5 5 7 8 0 8 8 7 3 5 9 0 9 0
3 7 2 6 7 9 9 1 2 3 2 9 7 9 0 5 3
4 3 3 5 1 7 1 5 5 7 6 4 5 4 6 2 0 5
9 116
6 6 4 1 7 7 7 9 2
6 4 3 2 8 3 1 6
1 1 1 1 3 5 6
9 3 0 0 3 8
1 1 3 2 0
8 3 8 9
3 0 7
5 4
1
0 7
1 8 7
2 8 5 9
9 9 3 6 4
6 9 3 3 1 3
4 5 8 2 0 5 4
2 5 0 9 0 9 7 1
4 2 1 0 3 5 6 9 6
7 81
8 3 1 0 7 6 0
2 3 6 3 5 8
2 1 1 0 3
1 9 4 7
2 9 7
3 6
0
2 9
3 0 8
6 7 6 2
6 1 0 7 6
5 1 7 2 4 3
3 3 2 9 2 0 6
7 77
7 9 5 5 0 2 7
8 1 2 7 7 0
7 1 7 3 1
7 3 8 2
8 8 2
2 7
7
5 3
6 8 4
1 1 7 2
2 9 2 7 7
5 1 1 3 1 0
2 4 8 4 3 4 9
11 154
5 7 8 5 7 1 8 4 7 6 0
6 2 5 5 1 2 8 4 4 4
3 8 8 5 9 1 3 7 9
9 7 5 6 0 8 7 1
5 0 9 9 6 3 2
0 4 8 9 8 3
0 4 4 7 0
6 2 5 7
4 0 3
3 0
9
8 8
6 5 3
5 5 6 0
2 0 6 9 0
7 0 4 3 1 6
7 1 8 2 4 1 5
4 0 0 4 8 9 6 2
7 4 8 8 0 4 2 4 7
0 4 5 4 3 9 6 8 4 3
0 5 0 8 8 3 4 5 8 4 0
19 194
9 5 0 1 4 0 8 8 2 0 9 3 2 5 1 4 0 0 9
2 1 4 5 2 3 4 1 9 5 6 5 4 7 9 0 8 0
1 0 4 6 7 8 6 6 8 9 0 6 7 4 4 8 8
3 0 1 3 6 8 9 8 6 0 7 2 3 2 2 6
9 1 1 5 4 5 2 4 8 3 4 9 9 7 8
4 7 5 2 8 1 7 0 1 1 8 9 0 9
0 1 3 6 2 6 1 0 6 6 5 5 3
6 2 9 4 9 1 8 7 8 7 1 0
2 9 0 1 1 4 3 0 2 3 8
4 5 3 9 4 2 4 7 0 2
4 9 8 3 3 7 7 0 6
3 8 8 0 2 7 5 6
9 0 7 5 0 7 2
7 3 0 5 2 9
7 4 8 4 3
1 3 4 4
8 0 0
8 6
4
1 8
5 8 0
7 5 8 5
5 5 0 9 4
1 5 5 7 1 1
0 7 1 5 4 8 8
1 1 6 5 2 7 1 3
8 4 9 2 6 4 9 6 1
7 2 5 3 6 1 3 9 2 8
2 9 0 7 8 5 7 9 2 5 9
1 8 1 1 6 2 6 4 0 1 8 9
3 9 2 8 7 1 2 0 6 7 2 5 2
0 9 4 4 9 3 8 8 4 6 7 0 9 2
8 7 4 9 6 6 0 1 9 3 6 3 1 1 2
6 8 8 9 5 9 5 4 8 4 5 5 9 1 4 5
4 0 5 1 4 1 6 5 9 0 3 6 4 7 9 9 7
2 3 7 8 6 7 1 2 9 7 7 0 7 9 6 3 1 8
5 1 4 8 2 8 2 5 1 9 3 8 5 4 2 6 5 8 2
19 304
8 4 4 8 5 3 5 4 3 4 8 0 9 1 2 8 6 0 3
3 7 2 6 1 9 9 0 0 7 1 5 4 6 1 7 5 3
9 0 1 8 6 4 4 7 5 0 1 3 5 4 0 8 6
7 5 2 0 4 2 2 4 6 1 2 9 7 9 2 0
8 4 6 0 3 5 7 2 7 7 9 3 3 1 2
6 1 8 2 3 2 3 5 8 5 7 5 7 4
4 2 3 4 3 4 9 9 3 7 1 8 9
5 6 5 6 2 2 8 8 1 9 8 3
6 9 0 1 0 0 7 1 1 1 8
9 3 8 9 0 8 1 7 5 0
4 6 7 4 5 5 1 8 5
5 4 4 0 5 9 1 9
8 6 1 1 8 3 9
7 8 6 4 5 5
9 0 6 9 8
3 9 1 9
7 4 4
5 2
7
3 2
2 6 2
5 9 1 1
1 4 3 0 2
3 0 9 7 1 8
0 3 5 7 2 2 8
1 8 8 3 3 1 7 6
8 8 8 6 7 3 7 3 2
5 6 8 5 9 3 8 0 4 0
4 0 7 2 4 4 7 8 5 4 2
6 1 7 6 3 3 8 3 2 0 8 4
1 9 5 4 6 5 6 2 3 5 7 7 5
5 4 0 3 0 3 6 4 7 8 9 4 2 4
4 6 1 0 4 5 2 0 9 6 0 0 4 8 6
1 2 6 6 3 9 0 4 1 2 5 4 1 5 2 3
4 2 0 1 7 8 1 4 1 0 0 8 7 9 1 0 6
5 1 1 8 5 5 7 8 5 6 3 9 5 1 5 7 4 6
6 1 1 7 2 2 1 2 5 1 1 7 7 5 0 1 0 7 1
2 26
1 7
5
3 1
3 47
6 8 1
1 0
8
9 2
8 9 3
15 178
1 7 0 3 0 6 7 6 9 3 4 5 0 5 2
6 6 1 0 0 8 8 9 0 3 4 6 4 3
1 3 9 4 4 8 3 1 0 7 7 5 2
1 6 8 5 5 4 3 8 7 6 7 1
2 4 0 1 0 8 7 4 2 4 4
4 3 9 7 6 9 5 6 0 2
9 7 6 2 1 0 3 1 4
4 8 4 8 8 3 2 8
7 3 4 2 5 4 1
5 9 3 6 3 3
4 2 1 6 0
5 4 0 0
0 8 7
2 0
7
0 2
3 3 7
2 0 5 1
9 6 1 4 4
5 7 0 7 9 4
2 6 8 1 4 5 2
1 3 0 8 2 7 9 1
6 4 9 0 3 4 9 6 4
9 5 6 5 8 5 4 4 6 9
2 8 1 4 2 4 2 7 9 7 6
9 4 1 4 3 9 5 7 7 0 5 0
6 6 6 1 9 8 5 5 1 3 4 8 0
6 5 5 3 2 4 8 8 2 4 6 7 2 1
0 0 8 2 1 0 7 2 5 8 8 5 2 7 3
10 114
0 9 6 1 4 9 8 8 7 7
2 5 5 3 5 2 4 2 3
0 0 5 4 3 6 1 7
6 2 2 8 4 1 9
3 0 8 3 1 4
3 4 9 4 8
4 4 1 3
4 9 4
5 0
4
2 2
1 8 1
9 8 2 9
9 3 9 8 7
1 9 1 4 2 3
0 5 9 3 7 0 0
2 1 6 2 2 1 3 1
5 8 6 3 2 6 4 3 2
4 1 0 4 1 7 3 9 2 8
7 100
3 4 6 0 1 3 7
9 5 5 5 2 0
1 3 4 7 5
8 4 4 0
7 1 3
7 2
5
5 8
8 5 2
2 2 4 6
6 3 3 0 1
7 1 8 1 0 0
9 5 2 4 9 0 4
19 250
4 9 7 1 0 8 3 0 7 6 4 0 2 5 9 0 9 7 5
5 7 1 0 7 5 0 6 8 7 0 5 3 0 2 2 5 0
8 0 7 5 0 4 6 2 9 7 3 6 5 4 8 3 8
4 8 7 6 5 2 8 1 8 3 0 9 9 1 1 5
8 6 4 7 1 2 2 4 3 4 7 7 4 8 6
4 4 9 1 1 3 2 4 9 9 8 3 8 8
7 1 9 1 7 7 1 2 3 9 5 8 3
4 9 6 2 3 6 8 3 7 5 4 1
2 2 9 6 8 9 3 6 3 0 2
1 5 6 0 4 2 8 0 6 6
5 6 6 8 6 0 1 3 4
5 8 0 8 7 6 9 7
6 9 6 0 7 9 4
4 1 2 7 1 7
5 5 9 3 5
8 6 2 1
1 2 4
4 8
5
6 5
1 2 5
0 0 3 8
0 9 9 3 0
5 5 8 9 6 8
9 7 6 3 7 6 7
9 8 7 9 5 8 5 7
1 1 1 4 3 2 5 7 3
8 1 1 1 7 6 8 2 0 2
6 8 2 4 9 1 7 4 6 0 9
8 5 1 9 9 8 9 2 9 4 0 8
6 7 3 0 1 9 9 7 7 1 3 6 0
5 0 9 2 9 5 4 4 0 0 5 6 7 5
4 9 8 5 8 8 8 6 8 4 6 1 0 1 4
3 9 6 2 9 5 4 5 4 3 7 2 6 5 1 0
4 4 9 2 8 4 7 3 6 2 8 4 2 1 8 9 4
5 7 7 0 1 9 5 6 6 0 0 6 0 7 7 7 7 6
8 1 8 2 8 1 2 8 3 8 9 7 2 2 5 2 3 9 9
18 306
0 8 4 6 5 4 3 1 6 1 2 2 0 6 9 7 1 4
7 2 1 7 4 4 7 6 3 6 0 6 6 2 5 3 8
9 5 3 0 7 7 2 3 4 5 1 8 5 6 4 0
0 4 4 2 8 7 3 9 7 5 6 3 5 2 4
6 4 9 4 1 5 5 6 6 5 8 0 4 5
2 8 4 3 3 2 9 5 6 8 0 0 2
7 0 8 5 7 1 5 3 7 7 8 7
0 6 9 1 9 4 0 7 4 6 2
2 5 6 0 7 5 4 3 5 0
7 0 1 6 6 5 9 2 4
7 3 1 1 7 0 4 0
0 4 0 0 7 9 3
4 5 2 2 6 4
2 6 4 2 5
6 2 5 7
4 5 2
4 1
9
6 1
1 8 9
5 5 7 1
4 0 5 2 2
3 2 0 2 7 8
2 5 5 0 0 9 4
6 2 2 2 1 1 3 5
9 1 1 2 4 5 7 9 1
2 2 6 2 3 7 5 8 3 2
7 4 4 1 6 9 9 9 0 3 6
4 4 7 8 3 6 0 7 8 4 1 8
4 5 4 9 0 4 8 7 6 7 7 5 3
4 5 0 3 4 8 3 3 8 1 8 1 3 8
8 5 5 9 8 8 7 7 3 4 2 4 3 1 2
9 0 9 2 9 4 2 3 7 2 5 0 0 9 3 3
7 6 0 0 2 3 4 5 7 2 6 5 1 8 9 2 8
0 4 2 9 1 0 9 1 9 5 0 5 7 8 1 6 2 4
4 49
4 2 3 1
2 3 5
3 4
9
9 9
9 8 9
5 6 1 6
14 176
6 7 3 4 7 4 4 1 9 5 1 7 3 3
5 4 3 5 1 8 7 5 9 6 5 0 4
5 3 0 6 1 6 8 1 8 8 9 8
3 3 3 7 8 7 6 2 4 7 8
5 8 2 6 1 8 5 7 6 9
5 6 3 2 4 2 6 3 0
4 2 3 0 0 8 4 3
8 7 7 6 1 1 1
5 9 6 7 6 6
6 9 7 2 4
5 0 9 0
9 3 1
5 8
0
6 3
5 9 7
3 4 6 4
5 4 6 3 2
4 4 2 1 1 7
2 6 9 7 9 2 3
3 4 0 4 2 4 5 5
0 2 1 7 0 4 5 3 5
0 5 0 5 5 4 6 1 1 1
5 7 0 1 0 2 1 0 8 5 1
0 0 0 5 0 1 8 7 2 5 0 2
8 9 0 5 2 1 3 7 5 0 7 2 2
2 8 5 6 9 7 0 1 9 1 0 3 5 2
10 99
3 1 7 1 6 9 3 4 0 9
5 5 6 2 7 6 2 7 9
4 1 9 3 1 6 2 0
8 8 8 9 6 3 8
6 3 8 7 5 3
4 5 7 0 7
8 5 2 7
9 2 1
0 7
2
9 2
3 5 0
6 5 9 4
0 9 4 9 9
8 9 3 8 2 5
0 4 8 5 1 3 7
9 7 1 9 8 6 6 9
2 0 3 7 3 1 5 5 9
8 7 5 8 9 4 0 0 1 2
13 215
2 5 9 2 1 9 5 7 5 3 7 5 3
0 3 9 7 2 2 5 5 5 8 5 5
1 3 0 6 1 5 6 0 5 2 7
3 7 3 7 1 9 7 4 2 0
7 2 5 7 2 8 6 2 8
6 7 4 1 0 9 8 7
7 5 4 1 4 8 0
9 7 3 2 4 8
2 5 4 9 6
9 3 3 2
7 9 9
0 5
4
6 9
4 5 8
2 7 2 6
3 8 5 5 1
4 5 1 8 6 0
0 4 7 1 0 9 4
8 2 7 6 4 8 9 7
0 5 4 2 5 2 1 5 6
0 4 1 7 2 2 2 9 9 2
8 8 3 8 9 7 7 6 4 3 3
4 4 8 8 6 0 9 2 7 4 0 2
2 3 9 5 3 7 4 8 2 9 2 9 1
17 241
1 5 8 1 7 5 2 1 8 1 6 5 4 7 6 4 7
9 5 3 2 3 6 4 0 2 8 7 6 7 3 0 5
7 0 8 2 9 1 0 3 3 2 9 9 0 9 9
0 4 6 2 8 2 8 1 9 7 1 8 3 7
0 0 7 6 7 9 3 3 4 9 5 9 2
6 7 6 8 7 7 4 9 8 1 9 5
6 1 5 1 9 5 7 9 9 9 1
4 8 9 3 4 3 7 1 5 8
2 9 8 0 0 9 4 7 9
9 5 3 7 8 7 8 5
6 8 1 0 5 2 0
5 4 5 0 5 0
8 7 0 6 1
3 0 6 2
7 3 2
1 8
4
2 9
5 5 8
3 9 4 7
1 8 2 7 3
7 2 4 8 3 4
0 6 3 8 7 7 6
7 0 4 5 4 8 6 8
1 2 0 6 9 6 3 5 5
7 5 8 4 6 6 4 7 1 0
8 5 1 0 4 5 2 9 6 7 8
9 9 7 0 5 8 8 7 3 4 7 5
8 7 7 9 2 4 1 1 9 7 3 4 6
5 4 8 3 7 4 3 0 4 7 9 2 6 3
1 6 9 3 2 3 5 6 2 6 7 6 3 7 2
4 3 1 9 6 3 0 2 5 5 2 6 9 6 6 4
4 4 1 5 4 7 9 0 9 4 5 0 6 5 1 3 0
18 314
4 8 9 4 3 0 9 9 1 3 8 2 8 6 7 0 4 6
3 4 5 7 9 0 1 4 6 4 8 5 9 5 5 6 8
0 4 2 8 2 8 8 4 0 8 2 8 2 7 7 3
2 0 2 6 7 5 4 4 1 7 8 4 5 0 2
7 5 2 3 7 8 7 7 3 7 8 4 1 8
0 7 9 2 2 8 7 5 7 8 7 5 4
7 4 1 9 5 7 7 5 3 1 3 9
0 5 4 4 6 3 6 8 3 2 1
5 4 7 9 5 1 8 8 4 4
6 5 2 3 8 3 1 7 6
4 8 1 9 1 3 0 9
2 5 5 1 1 9 6
2 7 7 6 8 2
7 3 5 4 5
9 4 4 2
7 9 0
9 9
7
9 3
2 1 9
4 1 9 5
0 4 2 2 4
9 3 2 4 5 6
3 9 3 2 2 0 7
8 1 4 8 3 4 5 5
3 2 3 4 1 2 0 4 5
5 5 4 3 7 4 0 4 6 9
1 2 4 8 6 0 6 2 8 6 1
0 4 0 6 1 1 6 2 4 5 0 4
8 4 5 5 5 8 2 2 7 2 1 9 1
3 7 8 3 4 3 9 2 5 6 1 6 4 9
6 0 6 9 6 4 9 5 3 9 7 1 9 0 0
0 9 9 8 6 3 0 8 7 2 7 4 8 3 1 1
8 2 7 7 0 6 3 1 0 8 0 1 4 8 6 9 6
7 7 7 0 0 1 4 9 5 0 2 1 2 0 7 6 7 1
6 78
6 7 6 1 4 4
7 8 8 1 3
4 3 9 6
6 7 2
5 3
7
8 1
0 0 5
8 8 4 1
3 3 6 2 3
5 0 4 0 7 5
7 114
2 8 3 6 1 3 7
7 8 6 3 3 0
5 0 2 5 7
5 9 0 5
4 7 3
3 9
7
4 6
8 8 3
1 3 7 5
9 6 1 3 9
4 5 4 5 3 4
0 1 9 3 0 8 1
5 76
9 1 4 2 2
2 0 1 0
5 1 1
1 3
5
7 2
5 7 3
4 1 4 2
7 0 7 2 8
6 54
5 0 7 9 2 5
7 3 9 6 5
3 4 5 0
9 9 4
0 1
9
0 1
8 6 7
8 1 9 7
7 3 2 9 5
9 5 9 4 2 3
14 192
3 1 4 0 4 4 6 5 0 1 8 7 1 5
9 6 9 5 3 9 6 2 3 1 2 8 0
3 5 8 8 4 6 3 0 5 2 9 6
6 7 7 3 8 7 0 9 4 8 1
8 3 8 6 7 9 4 4 8 0
6 7 8 0 8 1 5 9 3
7 9 5 2 9 0 2 7
9 7 9 2 2 0 1
2 9 0 1 4 8
9 5 0 9 6
9 5 8 3
0 6 5
5 0
5
0 3
9 7 7
9 3 5 5
5 5 7 8 6
0 4 9 1 8 7
3 2 7 6 3 5 4
4 3 1 5 4 1 2 1
3 7 1 0 6 4 5 9 4
6 3 0 7 1 0 5 1 5 8
8 9 9 1 1 0 6 0 1 5 2
8 2 4 8 1 2 2 3 4 7 4 2
4 0 7 9 6 6 7 2 6 2 1 0 4
3 4 3 5 6 1 1 6 7 8 9 3 5 3
19 244
7 4 3 8 9 0 8 5 2 8 9 0 5 2 5 9 1 0 3
2 3 1 1 1 4 1 8 5 6 3 3 0 5 5 5 5 3
9 9 3 4 6 3 4 0 8 3 3 1 0 1 3 5 3
4 5 8 6 9 7 4 7 7 3 6 5 9 8 8 4
5 8 8 5 3 5 7 0 5 6 6 8 8 8 9
9 3 6 2 9 1 9 1 9 8 8 6 0 5
4 4 1 0 5 9 7 4 2 1 8 0 4
5 7 7 3 8 0 7 8 4 8 6 6
6 3 3 3 1 8 1 3 1 5 1
9 3 6 7 8 4 0 9 3 6
9 0 8 2 6 5 9 2 6
7 1 5 3 2 3 3 8
8 6 8 8 6 3 0
5 5 7 9 3 5
7 1 0 6 2
2 7 8 7
6 5 1
9 2
6
5 0
2 5 1
8 9 8 8
3 8 9 5 9
6 5 2 4 8 4
8 0 5 8 3 4 2
4 5 4 1 3 3 8 0
1 0 7 9 8 1 3 4 4
9 3 6 8 9 6 5 4 1 7
7 7 7 6 0 6 2 0 4 6 5
3 4 8 6 3 4 9 2 4 6 2 0
4 7 9 6 1 5 7 3 5 3 0 8 3
0 6 3 6 0 7 5 2 6 8 7 1 1 5
8 1 9 3 1 9 2 5 3 9 6 8 4 3 5
4 7 8 9 6 6 9 7 2 5 7 5 0 6 6 8
8 2 2 3 6 3 6 9 0 7 3 3 2 8 7 5 8
2 2 3 6 0 7 2 0 0 4 4 5 7 5 9 1 9 2
7 0 5 7 3 6 7 0 8 4 7 8 8 0 3 0 2 4 9
15 246
5 0 0 5 1 1 5 3 8 1 4 5 1 8 8
0 3 9 9 2 3 0 3 8 8 5 6 4 1
2 6 9 7 8 6 8 4 7 4 4 1 9
2 3 7 7 5 8 5 5 6 7 0 7
4 2 2 7 8 7 2 5 9 3 3
1 2 1 6 8 4 9 4 6 1
9 4 4 2 3 4 4 5 8
8 1 4 0 8 1 9 7
0 1 4 0 9 0 7
4 7 3 2 5 2
9 0 3 7 0
9 1 4 8
3 3 1
1 5
3
1 5
0 4 1
3 1 2 4
2 6 0 4 6
5 8 1 8 5 8
4 5 4 2 8 6 9
5 7 2 4 9 2 0 4
3 0 3 9 0 7 2 5 8
6 0 5 1 3 5 5 2 5 0
5 6 9 4 0 6 3 7 2 6 9
2 3 4 3 6 9 5 9 1 4 0 9
8 3 3 5 2 1 3 3 3 7 6 0 2
6 7 9 9 9 6 8 8 5 2 4 8 2 7
4 1 2 5 9 7 8 1 0 5 7 2 3 3 9
8 87
5 9 0 1 3 4 7 2
3 6 4 0 2 2 9
6 7 0 9 9 7
8 6 6 3 1
3 9 1 2
4 5 0
7 7
8
9 2
4 9 0
8 0 7 4
2 3 3 2 9
2 1 8 6 6 9
8 0 8 1 1 6 6
6 7 8 6 2 6 5 0
11 176
9 6 1 3 4 5 3 7 4 2 5
8 5 8 4 5 9 1 6 2 4
6 8 8 6 1 8 6 7 5
3 6 9 5 0 8 8 9
0 5 3 9 2 1 5
4 1 4 1 9 0
8 0 6 6 6
4 3 8 7
5 2 5
5 6
8
1 2
2 7 4
7 0 0 6
6 6 0 2 9
6 4 7 5 6 4
6 9 9 9 4 4 7
5 7 1 8 3 1 0 1
6 4 2 6 7 1 5 1 3
8 8 5 2 9 4 2 6 4 6
2 5 1 0 7 0 4 9 8 1 6
3 41
0 1 7
0 1
6
3 3
6 5 1
13 220
5 3 3 5 6 6 7 0 5 3 9 3 5
9 3 2 8 7 8 6 9 1 8 7 8
0 7 6 3 9 6 0 0 8 3 7
9 6 9 2 1 5 2 4 8 3
8 4 3 1 9 7 0 2 7
9 9 4 0 6 7 9 7
8 8 3 6 0 8 3
7 5 7 3 2 3
3 4 5 7 2
1 3 9 3
3 8 7
3 0
0
8 9
6 0 4
9 9 3 4
5 3 1 7 9
7 0 7 8 1 8
5 0 7 2 0 6 3
1 5 4 3 9 0 4 6
4 0 9 0 9 9 4 5 7
8 0 4 7 2 1 8 2 8 0
6 3 8 5 1 7 7 5 7 4 9
6 6 5 0 1 7 4 7 3 9 4 0
4 9 4 7 1 9 6 4 9 9 1 3 9
14 145
6 4 4 4 3 9 9 4 0 9 2 9 2 3
2 7 4 3 7 1 9 9 9 5 9 2 4
6 2 8 9 3 9 3 9 5 2 8 8
4 1 3 0 4 1 0 2 2 2 9
3 6 6 5 0 9 2 2 6 3
0 8 3 0 8 9 2 6 6
9 6 1 5 8 6 2 7
6 4 6 5 5 2 3
6 7 3 0 1 6
9 5 3 2 2
9 6 8 4
0 1 6
3 4
0
7 3
8 4 6
1 6 6 4
1 6 4 8 9
6 0 1 2 2 8
4 9 8 9 5 2 7
9 8 8 6 0 2 0 6
7 3 9 2 5 2 7 3 9
0 7 1 9 1 7 6 1 9 9
1 1 8 5 0 8 5 1 0 7 9
8 3 4 5 9 9 4 9 0 7 1 1
8 9 2 4 5 0 6 3 9 3 0 1 2
3 7 1 3 4 1 3 0 6 1 4 5 4 1
9 113
9 1 4 9 4 9 7 7 1
9 2 8 3 0 3 2 5
2 5 0 6 0 6 4
4 8 9 6 7 4
7 6 8 9 1
7 0 4 6
8 2 0
9 9
0
6 2
4 5 7
0 7 5 2
4 5 3 8 0
2 9 4 6 9 2
3 6 8 9 8 1 5
1 7 0 9 2 0 1 0
5 4 8 9 0 0 3 2 7
4 57
2 7 1 4
0 3 7
6 5
2
1 7
0 6 1
5 2 1 3
0 0
Code: Select all
5675
0 RRRRRRRRRRRLRRLRLRRL
18331403
0 RRRRRRRRRRRRRRRLLLLLLLLLLRRLRL
59
14 LLLLLRLRLRRLLLLLLLRRRRRRRRRRRRRRRRRR
703854
4 LRRRRLRLRRRLRRRRRRRRRRRRLRRLRLRLRRRLLL
0
0
17315924
3 RLLRRRRRRRRRRRRRLRRLLRRRRRLLLLLLRRRRLR
0
22
0 RRRRRLLLLL
2
2 LRLLRL
110
1 RRRRLRRLRLRR
0
0
0
1
6 LLLRRLLLRRLRLLLLRRLR
147054
3 RRRRRRRRLRLLRRRRRRRRRRRRRRRRRR
0
51722
4 RRRRRRRRRRLLRRRLLLLLLLLRRRRLRLRLRL
0
0
0
444575
0 RRRRRRRRRRRRRRLLLLLRRRRLLLLR
5
6 RRLRRRRRLLLLLRRRRRRRRRRRRRRR
0
0
0
938
4 RRRRRRRRLLRLRLLLLLRRLLLLLLLL
0
0
0
5810
4 RRRRRLRRRRRRLLLRRRRRRRRRRRRRRRRR
0
0
0
4
2 RLLRLRLR
3058355
0 RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
0
0
0
527914
0 RRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
0
0
0
6462
1 RRRRRRRRRRRLRLLLLLLRRLLRRL
0
387866994
0 RRRRRRRRRRRRRRRRRLLLLLLLLLLLLRRRRL
0
0
20
0 RRRRRRLRRLLL
0
432226083
0 RRRRRRRRRRRRRRRRRRLLLLLLLLLRLLLRLLRL
2090726
1 RRRRRRRRRRRRRRLRRRRRRRRRRRRRRRRRRRRR
0
0
0
50
4 RRLLRLRLRLLLLRRLLR
0
0
1955331
0 RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
0
0
7827
0 RRRRRRRRRLLLRRLLLR
0
0
1757070
0 RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
0
0
0
49
0 RRRRRLLRLR
0
10663
7 RRRLRRRLLRRLRRLLLRLRLLLRLLLLLLLLRRRR
22
1 RRRRRRRRRRRLRRRRRRRRRRRRRRRR
188
0 RRRRRRRLRLLRLR
0
0
0
149616
0 RRRRRRRRRRRRRLLRLLLLRRLRLR
19
0 RRRRRRRRLRLLLRRL
0
Last edited by ImLazy on Tue Sep 20, 2005 7:36 am, edited 1 time in total.
I stay home. Don't call me out.
-
- A great helper
- Posts: 481
- Joined: Sun Jun 19, 2005 1:18 am
- Location: European Union (Slovak Republic)
Re: #10564, If you AC, please check my output for this input
My AC's output is:
Code: Select all
5675
0 RRRRRRRRRRRLRRLRLRRL
18331403
0 RRRRRRRRRRRRRRRLLLLLLLLLLRRLRL
0
703854
4 LRRRRLRLRRRLRRRRRRRRRRRRLRRLRLRLRRRLLL
0
0
17315924
3 RLLRRRRRRRRRRRRRLRRLLRRRRRLLLLLLRRRRLR
0
22
0 RRRRRLLLLL
2
2 LRLLRL
110
1 RRRRLRRLRLRR
0
0
0
1
6 LLLRRLLLRRLRLLLLRRLR
0
0
51722
4 RRRRRRRRRRLLRRLLRLLLLLLRRRRLRRRLLL
0
0
0
444575
0 RRRRRRRRRRRRRRLLLLLRRRRLLLLR
0
0
0
0
938
4 RRRRRRRRLLRLRLLLLLRRLLLLLLLL
0
0
0
0
0
0
0
4
2 RLLRLRLR
0
0
0
0
0
0
0
0
6462
1 RRRRRRRRRRRLRLLLLLLRRLLRRL
0
387866994
0 RRRRRRRRRRRRRRRRRLLLLLLLLLLLLRRRRL
0
0
20
0 RRRRRRLRRLLL
0
432226083
0 RRRRRRRRRRRRRRRRRRLLLLLLLLLRLLLRLLRL
0
0
0
0
50
4 RRLLRLRLRLLLLRRLLR
0
0
0
0
0
7827
0 RRRRRRRRRLLLRRLLLR
0
0
0
0
0
0
49
0 RRRRRLLRLR
0
10663
7 RLRRRRRLLRLRRRLLLRLRLLLRLRRRRRRRRRRL
0
188
0 RRRRRRRLRLLRLR
0
0
0
149616
0 RRRRRRRRRRRRRLLRLLLLRRLRLR
19
0 RRRRRRRRLRLLLRRL
0
Dear Martin Macko, can you give me your output for this input data? Thanks.
http://baidiheizi.diy.myrice.com/bbs/in.txt
There are 1000 cases in this input file.
http://baidiheizi.diy.myrice.com/bbs/in.txt
There are 1000 cases in this input file.
I stay home. Don't call me out.
-
- A great helper
- Posts: 481
- Joined: Sun Jun 19, 2005 1:18 am
- Location: European Union (Slovak Republic)
The inputs and outputs are (gzipped) at http://www.ksp.sk/~martin/val/10564/ImLazy wrote:Dear Martin Macko, can you give me your output for this input data? Thanks.
good luck
-
- A great helper
- Posts: 481
- Joined: Sun Jun 19, 2005 1:18 am
- Location: European Union (Slovak Republic)
Well... have you (double)checked all special cases? N=2; N=20; S=0; All cells with the same value; Or write a bruteforce for small N and compare the outputs for all possible inputs (for small N).ImLazy wrote:The same output as yours and still WA.
I think I should give it up now.
Thank you anyway, Martin Macko.
If nothing helps, post your code here... If I'll have time I'll look at it...
Dear Martin Macko, I've got AC!
I used to divide the hourglass into two pyramids, the top one and the bottom one, and count the paths respectively. Because I thought this can be faster. But this method complicate the problem and caused WA.
Today I retyped my code and this time I didn't divide the hourglass. Soon I got AC.
Thank you for giving me so much help.![:)](./images/smilies/icon_smile.gif)
I used to divide the hourglass into two pyramids, the top one and the bottom one, and count the paths respectively. Because I thought this can be faster. But this method complicate the problem and caused WA.
Today I retyped my code and this time I didn't divide the hourglass. Soon I got AC.
Thank you for giving me so much help.
![:)](./images/smilies/icon_smile.gif)
I stay home. Don't call me out.
-
- A great helper
- Posts: 481
- Joined: Sun Jun 19, 2005 1:18 am
- Location: European Union (Slovak Republic)
Could you, please, delete the wrong outputs to make sure we won't confuse somebody?ImLazy wrote:Dear Martin Macko, I've got AC!
I used to divide the hourglass into two pyramids, the top one and the bottom one, and count the paths respectively. Because I thought this can be faster. But this method complicate the problem and caused WA.
Today I retyped my code and this time I didn't divide the hourglass. Soon I got AC.
Thank you for giving me so much help.
Re: 10564 - Paths through the Hourglass
I have gotten Wrong, However , I can't find the mistake, Please help me Check The Code?
My Idea: First I use the DP to get the sum of the paths, Then, I use the DFS to find out the best path.
==========================================>>I got Wrong Answer
Help!
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
int map[25][25];
int f[42][42][502];
int g,s,n;
char ss[100];
int ll;
void dfs(int x,int y,int u,int be)
{
if (map[x][y]<0)return;
if (x==2*n-1&&u==s) {printf("%d ",be-1);g=1;return;}
if (x==2*n-1||(x<2*n-1&&u>s))return;
if (x<n)
{
{dfs(x+1,y-1,u+map[x+1][y-1],be); if (g){ss[x]='L';;return;}}
{dfs(x+1,y,u+map[x+1][y],be); if (g){ss[x]='R';return;}}
}
else
{
{dfs(x+1,y,u+map[x+1][y],be); if (g){ss[x]='L';return;}}
{dfs(x+1,y+1,u+map[x+1][y+1],be); if (g){ss[x]='R';return;}}
}
}
int main()
{
freopen("1.txt","r",stdin);
freopen("2.txt","w",stdout);
int i,j,k,l,m;
while (scanf("%d%d",&n,&s))
{
if (n==0) break;
memset(map,-1,sizeof(map));
memset(f,0,sizeof(f));
for (i=1;i<=n;i++)
for (j=1;j<=n-i+1;j++)
scanf("%d",&map[j]);
for (i=1+n;i<=n+n-1;i++)
for (j=1;j<=i-n+1;j++)
scanf("%d",&map[j]);
memset(f[1],0,sizeof(f[1]));
for (i=1;i<=n;i++)
if (map[1]>=0)
f[1][map[1]]=1;
for (i=2;i<=n;i++)
for (j=1;j<=n;j++)
{
if (map[j]<0) break;
for(k=s;k>=0;k--)
{
f[j][k]=0;
if (k>map[j])
{
int g1=0,g2=0;
g1=f[i-1][j][k-map[j]];
g2=f[i-1][j+1][k-map[j]];
if (map[i][j]>=0)
f[i][j][k]+=(g1+g2);
}else break;
}
}
for (i=n+1;i<=2*n-1;i++)
for (j=1;j<=n;j++)
{
if (map[i][j]<0) break;
for(k=s;k>=0;k--)
{
f[i][j][k]=0;
if (k>map[i][j])
{
int g1=0,g2=0;
g1=f[i-1][j][k-map[i][j]];
g2=f[i-1][j-1][k-map[i][j]];
if (map[i][j]>=0)
f[i][j][k]+=(g1+g2);
}else break;
}
}
int sum=0;
for (i=1;i<=n;i++)
sum+=f[2*n-1][i][s];
printf("%d\n",sum);
if (sum)
{
memset(ss,0,sizeof(s));
g=0;
for (i=1;i<=n;i++)
{dfs(1,i,map[1][i],i);if(g)break;}
int len=strlen(ss);
if (g) for (i=1;i<=2*n-2;i++)printf("%c",ss[i]);
}
printf("\n");
}
return 0;
}
My Idea: First I use the DP to get the sum of the paths, Then, I use the DFS to find out the best path.
==========================================>>I got Wrong Answer
Help!
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
int map[25][25];
int f[42][42][502];
int g,s,n;
char ss[100];
int ll;
void dfs(int x,int y,int u,int be)
{
if (map[x][y]<0)return;
if (x==2*n-1&&u==s) {printf("%d ",be-1);g=1;return;}
if (x==2*n-1||(x<2*n-1&&u>s))return;
if (x<n)
{
{dfs(x+1,y-1,u+map[x+1][y-1],be); if (g){ss[x]='L';;return;}}
{dfs(x+1,y,u+map[x+1][y],be); if (g){ss[x]='R';return;}}
}
else
{
{dfs(x+1,y,u+map[x+1][y],be); if (g){ss[x]='L';return;}}
{dfs(x+1,y+1,u+map[x+1][y+1],be); if (g){ss[x]='R';return;}}
}
}
int main()
{
freopen("1.txt","r",stdin);
freopen("2.txt","w",stdout);
int i,j,k,l,m;
while (scanf("%d%d",&n,&s))
{
if (n==0) break;
memset(map,-1,sizeof(map));
memset(f,0,sizeof(f));
for (i=1;i<=n;i++)
for (j=1;j<=n-i+1;j++)
scanf("%d",&map[j]);
for (i=1+n;i<=n+n-1;i++)
for (j=1;j<=i-n+1;j++)
scanf("%d",&map[j]);
memset(f[1],0,sizeof(f[1]));
for (i=1;i<=n;i++)
if (map[1]>=0)
f[1][map[1]]=1;
for (i=2;i<=n;i++)
for (j=1;j<=n;j++)
{
if (map[j]<0) break;
for(k=s;k>=0;k--)
{
f[j][k]=0;
if (k>map[j])
{
int g1=0,g2=0;
g1=f[i-1][j][k-map[j]];
g2=f[i-1][j+1][k-map[j]];
if (map[i][j]>=0)
f[i][j][k]+=(g1+g2);
}else break;
}
}
for (i=n+1;i<=2*n-1;i++)
for (j=1;j<=n;j++)
{
if (map[i][j]<0) break;
for(k=s;k>=0;k--)
{
f[i][j][k]=0;
if (k>map[i][j])
{
int g1=0,g2=0;
g1=f[i-1][j][k-map[i][j]];
g2=f[i-1][j-1][k-map[i][j]];
if (map[i][j]>=0)
f[i][j][k]+=(g1+g2);
}else break;
}
}
int sum=0;
for (i=1;i<=n;i++)
sum+=f[2*n-1][i][s];
printf("%d\n",sum);
if (sum)
{
memset(ss,0,sizeof(s));
g=0;
for (i=1;i<=n;i++)
{dfs(1,i,map[1][i],i);if(g)break;}
int len=strlen(ss);
if (g) for (i=1;i<=2*n-2;i++)printf("%c",ss[i]);
}
printf("\n");
}
return 0;
}
-
- New poster
- Posts: 5
- Joined: Tue Aug 16, 2011 11:15 am
Re: 10564 - Paths through the Hourglass
????long long