OJ Board

Posted: **Wed Oct 15, 2003 12:25 am**

Read up on dynamic programming, and you'll see. Basically, it's a way of caching values so that you don't keep on computing the same values. You can look at it as trying all possible paths, but ifyou know the answer at the current "node", then you just return what you stored already instead.

Posted: **Fri Oct 17, 2003 2:53 am**

Ok, solved!! I just did not think enough before...

I've created a 20x40x351 matrix to store parcial values...

But, how do I solve this with < 0.09 sec with 64k of memory?

JP.

Posted: **Fri Oct 17, 2003 6:35 pm**

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.

Posted: **Sat Nov 27, 2004 1:20 pm**

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.

Posted: **Fri Sep 09, 2005 12:31 pm**

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

My output is:

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

Is this the same as yours? Thanks.

Posted: **Sun Sep 11, 2005 9:30 am**

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

Posted: **Mon Sep 19, 2005 5:55 pm**

Thank you, Martin Macko.Now my programe have the exactly same output with you. But still WA. I'm getting crazy.

Posted: **Tue Sep 20, 2005 7:23 am**

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.

Posted: **Fri Sep 23, 2005 3:41 am**

ImLazy wrote:Dear Martin Macko, can you give me your output for this input data? Thanks.

The inputs and outputs are (gzipped) at http://www.ksp.sk/~martin/val/10564/

good luck

Posted: **Sun Sep 25, 2005 11:14 am**

The same output as yours and still WA.
I think I should give it up now.
Thank you anyway, Martin Macko.

Posted: **Sun Sep 25, 2005 10:35 pm**

ImLazy wrote:The same output as yours and still WA.
I think I should give it up now.
Thank you anyway, Martin Macko.

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).

If nothing helps, post your code here... If I'll have time I'll look at it...

Posted: **Sat Oct 01, 2005 4:06 pm**

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.

Posted: **Sun Dec 11, 2005 12:41 am**

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.

Could you, please, delete the wrong outputs to make sure we won't confuse somebody?

Posted: **Sun Nov 28, 2010 10:13 am**

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;
}

Posted: **Sat Aug 27, 2011 5:30 am**

????long long

OJ Board

10564 - Paths through the Hourglass

a late reply..

10564

Re: #10564, If you AC, please check my output for this input

Re: 10564 - Paths through the Hourglass

Re: 10564 - Paths through the Hourglass