两人玩一游戏，在他们面前有一堆石头，数量为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]]

懂你说的，你的意思是：如果我们拿了之后剩余的石子数是三的倍数即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]]

对于第三种情况后拿者是否一定能取胜
  如果第一个人拿了一个(或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);
这样行吗？

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

讲的太对了，确实~~。