Description

有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目,如果轮到你先取,假设双方都采取最好的策略,问最后你是胜者还是败者。

Input

输入包含若干行,表示若干种石子的初始情况,其中每一行包含两个非负整数a和b,表示两堆石子的数目,a和b都不大于1,000,000,000。

Output

输出对应也有若干行,每行包含一个数字1或0,如果最后你是胜者,则为1,反之,则为0。

 

assuming input is (a, b), a is alway less than b, say a to be part0, say b to part1

  1. if a = b,print 1
  2. if (a,b) = (1,2) , print 0
  3. if (a,b) = (1,n), n>2
    firstly get n-2, then it can be reduced to scenario 2
    so print
    1
  4. if (a,b) = (2, n), n>2
    if I get 1from part0, it is reduced to (1,n), so I lose. excluding it
    if I get 2 from part0, it is reduced to (0,n), so I lose, excluding it
    So I can only get from part1. get n-1 from part1, reduce it to scenario 2
    so print
    1
  5. if (a,b) = (3, n), n>3
    can not get 1, or 2, or 3 from part0, it will lose   
        if n=4, (3,4) reduce to (3,3), lose
                    (3,4) reduce to (3,2), lose
                    (3,4) reduce to (3,1), lose
                    (3,4) reduce to (3,0), lose
              print 0 for (3,4)
        if n>4, reduce (3,n) to (3,4) by get n-4 from part1
              print 1 for (3,n) n>4
  6. if (a,b) = (4, n), n>4
    (4,n) reduce to (4,3) by get n-3 from part1
    print 1
  7. if(a,b) = (5, n), n>5
    can not get 1,2,3,4,5 from part0, will lose
  8.     if n=6, (5,6) reduce to (5,5), lose
                    (5,6) reduce to (5,4), lose
                    (5,6) reduce to (5,3), lose
                    (5,6) reduce to (5,2), lose
                    (5,6) reduce to (5,1), lose
                    (5,6) reduce to (5,0), lose
              print 0 for (5,6)
        if n>6, reduce (5,n) to (5,6) by get n-6 from part1
              print 1 for (5,n) n>6

  9. if(a,b) = (6, n), n>6
    (6,n) reduce to (6,5) by get n-5 from part1
    print 1

So we can see something here, summarize as such:

 

  • if a=b, ouput 1
  • sort the pair to be (a,b) to meet a<b
    if a=2n, output 1
    if a=2n+1, b=2n+2, output 0
    if a=2n+1, b>2n+2, output 1
0 n 1
1 2 0
1 n(>2) 1
2 n(>2) 1
3 4 0
3 n(>4) 1
4 n(>4) 1
5 6 0
5 n(>6) 1
6 n(>6) 1
7 8 0
7 n(n>8) 1

Advertisements