10564 - Paths through the Hourglass

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » 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.

jpfarias
Learning poster
Posts: 98
Joined: Thu Nov 01, 2001 2:00 am
Location: Brazil
Contact:

Post by jpfarias » 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.

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:

Post by Yarin » 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.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

a late reply..

Post by sohel » 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. :-?

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

10564

Post by ImLazy » 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.
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.

User avatar
Martin Macko
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

Post by Martin Macko » 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


User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » 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.
I stay home. Don't call me out.

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » 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.
I stay home. Don't call me out.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » 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

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » 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.
I stay home. Don't call me out.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » 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...

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » 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. :)
I stay home. Don't call me out.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » 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?

zslwyuan
New poster
Posts: 4
Joined: Sun Nov 28, 2010 10:04 am

Re: 10564 - Paths through the Hourglass

Post by zslwyuan » 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;
}

CSGrandeur
New poster
Posts: 5
Joined: Tue Aug 16, 2011 11:15 am

Re: 10564 - Paths through the Hourglass

Post by CSGrandeur » Sat Aug 27, 2011 5:30 am

????long long

Post Reply

Return to “Volume 105 (10500-10599)”