## 10561 - Treblecross

Moderator: Board moderators

dapumptu
New poster
Posts: 5
Joined: Tue Nov 25, 2003 3:30 pm
Can someone help me check my grundy number for n= 0~44
, is it right????

0~9
011123034
10~18
111030321

250301212

303412103

032125030

gush
New poster
Posts: 13
Joined: Tue Oct 14, 2003 12:47 pm
the output should be as follows.

WINNING
3
LOSING

WINNING
3
WINNING
1 12 15 17 20 24 28 31 33 36 47
WINNING
3 5
WINNING
4 10 16 22 23 33 34 35 37 38 39 49 50 51
WINNING
17 20
WINNING
1 4 5 6 9
WINNING
3 6
WINNING
3
WINNING
11
WINNING
12
WINNING
3 12
WINNING
13 16
LOSING

WINNING
12 15
WINNING
11
WINNING
7
WINNING
1 3 7 8 17 18 19 28 29 33 35
WINNING
12 15
LOSING

WINNING
52 53 55 56
WINNING
23 29

gush
New poster
Posts: 13
Joined: Tue Oct 14, 2003 12:47 pm
the output should be as follows.

WINNING
3
LOSING

WINNING
3
WINNING
1 12 15 17 20 24 28 31 33 36 47
WINNING
3 5
WINNING
4 10 16 22 23 33 34 35 37 38 39 49 50 51
WINNING
17 20
WINNING
1 4 5 6 9
WINNING
3 6
WINNING
3
WINNING
11
WINNING
12
WINNING
3 12
WINNING
13 16
LOSING

WINNING
12 15
WINNING
11
WINNING
7
WINNING
1 3 7 8 17 18 19 28 29 33 35
WINNING
12 15
LOSING

WINNING
52 53 55 56
WINNING
23 29

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:
Hi.
I read up some math, and solved this problem. But I did not understand the all background of this.. (I'm really bad in math )

I believe there should be another approach that is not based on game theory, and it is much more likely the "another method" is feasible for real contest environments. (Looking at Yarin's 0.15sec time confirmed it )

I tried to find one, but it was not easy.

Could anybody offer a helping hand? I'll greatly appreciate it.

Best regards,
JongMan
JongMan @ Yonsei

Andrey Mokhov
Experienced poster
Posts: 128
Joined: Fri Nov 15, 2002 7:45 am
Location: Kyrgyzstan
Hello, Whinii F.!

Why don't you like this method? To my mind it was one of the most beautiful problems and one of the best of my solutions!!

Great thanks to Jimmy M

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:
Hi Andrey!

I just thought so because I am not good at math at all. Suppose that I faced this kind of problem in an actual contest environment. I don't think I would solve it, since I don't know this particular theory. So I just imagined of a different solution that can deal with some more general situations.

(Yeah, give some chance to those who are not good at math! )

That was all. It was not intention, at all, to mean that the method was not good.

Thanks for paying attention.

And dapumptu:

Your table seems to be different from mine. My AC program has a table like:

0 ~ 9: 0 1 1 1 2 2 0 3 3 1
10 ~ 19: 1 1 0 4 3 3 3 2 2 2
20 ~ 29: 4 4 0 5 5 2 2 2 3 3
30 ~ 39: 0 5 0 1 1 1 3 3 3 5
JongMan @ Yonsei

Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm
here are some test cases:
• 39
XX.....
.....XX
...XX.
.XX...
.XX.X..XX.XX.
...
XX.
.XX
.X.
X.X
X..
..X
.....
X.....X..X.............X....X..X
.X.X...X
...............................................
.X.X.X.................X...X.............X......
X...........X.....X......X...................X.....
.....X...........XX......
.........
.X.XX...
.......X
...........XX
.X..........XX
XX..........XX
.X.......X......
X................X.
X.......X........X....X...X
.....................
.............
...................................
............XX..........
.........X.......................................X......
.......................X......X.................X.......
.X..............X.................X..........
..................................................
....................................................................................................
......................................................................................................................................................
........................................................................................................................................................................................................
• WINNING
3
WINNING
5
WINNING
3 6
WINNING
1 4
WINNING
1 4 7 10 13
WINNING
1 2 3
WINNING
3
WINNING
1
LOSING

WINNING
2
LOSING

LOSING

WINNING
3
LOSING

WINNING
3
WINNING
1 12 15 17 20 24 28 31 33 36 47
WINNING
3 5
WINNING
4 10 16 22 23 33 34 35 37 38 39 49 50 51
WINNING
17 20
WINNING
1 4 5 6 9
WINNING
3 6
WINNING
3
WINNING
11
WINNING
12
WINNING
3 12
WINNING
13 16
LOSING

WINNING
12 15
WINNING
11
WINNING
7
WINNING
1 3 7 8 17 18 19 28 29 33 35
WINNING
12 15
LOSING

WINNING
52 53 55 56
WINNING
23 29
WINNING
5 10 11 13 14 19 21 22 29 30 32 37 38 40 41 46
WINNING
7 8 18 50 51 83 93 94
WINNING
40 111
WINNING
5 11 21 22 24 26 34 38 45 50 64 65 69 75 78 81 91 93 94 96 97 104 105 107 108 110 120 123 126 132 136 137 151 156 163 167 175 177 179 180 190 196
hope it helps. you should get AC if you can pass the above cases.
Not all of our dreams can be made to come true. But still we live with the hope to turn them into reality someday.

Sana
New poster
Posts: 1
Joined: Wed Apr 07, 2004 6:02 pm

### 10561 can some one help me out?

I ve never submitted a problem on acm and this problem was assigned to me as my course assignment and it has quite heavy weitage and i am unable to solve it as am not good in Math..its due on 11 April can some one help me out with it? i ll be really thank full. if some one cant give me a sample solution if he can help me atleast to make up the logic it will be okay.. time is very short for me.
Sana.

BiK
Experienced poster
Posts: 104
Joined: Tue Sep 23, 2003 5:49 pm
Marian or everybody else,

Do you know some good books about Grundy-Sprague numbers?

Thanks

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Contact:

### Re: 10561 - Treblecross

Can anyone tell me whether I could check X.X type cases directly using grundy numbers or I just need to check them manually?
And for finding winning positions, if I check manually and using grundy at the same time, will it cause any trouble? Here, I mean by manual checking are those cases like XXX... or ...XXX or .....X.X..... ?
Thanks
You should not always say what you know, but you should always know what you say.

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Contact:

### Re: 10561 - Treblecross

I got AC today, but the following IO doesn't match with 'Dreamer#1's output:

Code: Select all

``````1
........................................................................................................................................................................................................
``````
His output:

Code: Select all

``````WINNING
5 11 21 22 24 26 34 38 45 50 64 65 69 75 78 81 91 93 94 96 97 104 105 107 108 110 120 123 126 132 136 137 151 156 163 167 175 177 179 180 190 196
``````
My output:

Code: Select all

``````WINNING
1 9 12 44 63 84 87 90 111 130 162 165 173
``````
From this, I guess my solution is wrong and judge data doesn't contain this. Can anyone else check ?
You should not always say what you know, but you should always know what you say.

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm