OJ Board

Can someone help me check my grundy number for n= 0~44
, is it right????


0~9
011123034
10~18
111030321

250301212

303412103

032125030

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

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

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

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

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

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.

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.

Marian or everybody else,

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

Thanks

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

I got AC today, but the following IO doesn't match with 'Dreamer#1's output: His output: My output: From this, I guess my solution is wrong and judge data doesn't contain this. Can anyone else check ?

Now it's ok