两人玩一游戏，在他们面前有一堆石头，数量为n,双方轮流取石头，条件是取的石头的数目是非负的整数且是2的幂（例如1，2，4，8等），拿到最后一个石头的人获胜，假设双方都是尽力想要取胜的。



编一道程序来解决问题，，使得输入石头的总数后，输出哪方获胜且第一次拿的石头数。


上面是我翻译的，下面是原题。

Two Nikifors play a funny game. There is a heap of N stones in front of them. Both Nikifors in turns take some stones from the heap. One may take any number of stones with the only condition that this number is a nonnegative integer power of 2 (e.g. 1, 2, 4, 8 etc.). Nikifor who takes the last stone wins. You are to write a program that determines winner assuming each Nikifor does its best.

Input
An input contains the only positive integer number N (condition N ≤ 10250 holds).

Output
The first line of an output file should contain 1 in the case the first Nikifor wins and 2 in case the second one does. If the first Nikifor wins the second line should contain the minimal number of stones he should take at the first move in order to guarantee his victory.

Sample
input
8
output
1
2

 
有谁能分析一下题目？十分感谢。

[[it] 本帖最后由 xujie3 于 2008-8-21 14:26 编辑 [/it]]

输入一个N,如果N=3M+1,就取一个(或3X+1个,且3X+1=2^Y);
如果N=3M+2,就取2个(或3X+2个,且3X+2=2^Y);
如果N=3M,没办法,坐以待毙.

因为对3M,减去2^Y,无论Y是几,都不会等于3n,因为如果
3M-2^Y=3n,则3(M-N)=2^Y,而2^Y中没有因子3.

懂你说的，你的意思是：如果我们拿了之后剩余的石子数是三的倍数即3M，我们就赢了。非常谢谢！但是第三种情况按你的说法这程序就编不出来了，这得再想想，希望不懂能和你多多交流。

1
   2 #include <stdio.h>
   3 #include <ctype.h>
   4
   5 int main() {
   6     char c;
   7     int i = 0;
   8     while(scanf("%c", &c) != EOF) {
   9         if(isdigit(c)) {
  10             i += c-'0';
  11         }
  12     }
  13     if(i%3==0)
  14         printf("2");
  15     else
  16         printf("1\n%d", i%3);
  17 }


这是参考的一个程序，我看不懂，能帮忙看下吗？

[[it] 本帖最后由 xujie3 于 2008-8-21 20:32 编辑 [/it]]

楼上的意思是想在N=3M时仍然可以胜,这显然是没有看懂上面的证明.下面我用另外一种思路来说明:
假设N=3M时仍然可以胜,就等同于不管N是几,只要谁先拿,谁就可以胜.如果这种情况存在,那么A先取后,N剩余为N1,B作为后拿者,不管怎么拿,都是输.

但现在假设A先拿,面对的就是N1,他也会胜.而实质这和B的情况是完全一样的.所以是不可能的.
所以不存在不管N是几,只要谁先拿,谁就可以胜的情况

对于第三种情况后拿者是否一定能取胜
  如果第一个人拿了一个(或3X+1个,且3X+1=2^Y)，后来的人就取2个(或3X+2个,且3X+2=2^Y);
  如果第一个人拿了2个(或3X+2个,且3X+2=2^Y)，后来的人就取一个(或3X+1个,且3X+1=2^Y);
这样行吗？

上面那个程序好像运行有点问题

讲的太对了，确实~~。

关于这个问题,还可以设计为谁拿到最后一个谁输.算法大同小异

对simpley兄的逻辑思维和推算能力真是佩服，特别是你用的那个反证法真是精妙啊！

下面是我仿照simpley兄的思路，对“谁拿到最后一个谁输”描述的算法，请看看对不对！

输入一个N,如果N=3M,就取2个,剩 3X+1,且X=M-1;
如果N=3M+2,就取1个,也是剩 3X+1,且X=M-1;
如果N=3M+1,没办法,坐以待毙.

因为对3M+1,减去2^Y,无论Y是几,都不会等于3n+1,因为如果
(3M+1)-2^Y=3n+1,则3(M-n)=2^Y,而2^Y中没有因子3.