POJ 2484 A Funny Game - Game Theory

POJ 2484 A Funny Game - Game Theory
Alice and Bob decide to play a funny game. At the beginning of the game they pick n(1 <= n <= 10⁶) coins in a circle, as Figure 1 shows. A move consists in removing one or two adjacent coins, leaving all other coins untouched. At least one coin must be removed. Players alternate moves with Alice starting. The player that removes the last coin wins. (The last player to move wins. If you can't move, you lose.) 

Figure 1
Note: For n > 3, we use c1, c2, ..., cn to denote the coins clockwise and if Alice remove c2, then c1 and c3 are NOT adjacent! (Because there is an empty place between c1 and c3.) 

Suppose that both Alice and Bob do their best in the game. 
You are to write a program to determine who will finally win the game.

Input

There are several test cases. Each test case has only one line, which contains a positive integer n (1 <= n <= 10⁶). There are no blank lines between cases. A line with a single 0 terminates the input. 

Output

For each test case, if Alice win the game,output "Alice", otherwise output "Bob". 

Sample Input

1
2
3
0

Sample Output

Alice
Alice
Bob

http://www.cnblogs.com/fenshen371/p/3288007.html

题意：n枚硬币围成一个圈，每次每个人可以从中取走一枚或者相邻的两枚（如果两枚硬币原本中间隔着一枚硬币，后来被取走，这两枚硬币不算相邻）。谁取走最后一枚硬币谁就赢了。

思路：我们可以找找规律。

首先，n为1和2的时候肯定是先手胜。n为3时，无论先手取1枚还是2枚，都会输。

当n大于等于4时，我们分成两种情况来讨论。

如果n为偶数，对于后手来说，总可以根据先手的做法，在对称的位置取走相同数量的硬币。先手必输。

如果n为奇数，对于后手来说，总可以在某处取走硬币后，使得剩下的硬币分成对称的两组，然后依照n为偶数时的策略就能赢。此时也是先手必输。

这个题可以证明若n>=3，则先手必败。
对称博弈
若n>=3，先手第一次必然把这个环拆成一个链，然后无论这条链长度的奇偶，后手总是可以把这条链分成两条相等的链，于是先手在一条链上做什么，后手就可以做什么。知道先手无法操作，后手胜。

在游戏中，作出对称的状态后再完全模拟对手的策略常常是有效的。

int main()
 3 {
 4     int n;
 5     while (~scanf("%d", &n) && n)
 6     {
 7         if (n > 2) printf("Bob\n");
 8         else printf("Alice\n");
 9     }
10     return 0;
11 }