[游戏开发][巴什博弈][找规律]A Childhood Game LightOJ1020

Alice and Bob are playing a game with marbles; you may have played this game in childhood. The game is playing by alternating turns. In each turn a player can take exactly one or two marbles.

Both Alice and Bob know the number of marbles initially. Now the game can be started by any one. But the winning condition depends on the player who starts it. If Alice starts first, then the player who takes the last marble loses the game. If Bob starts first, then the player who takes the last marble wins the game.

Now you are given the initial number of marbles and the name of the player who starts first. Then you have to find the winner of the game if both of them play optimally.

Input

Input starts with an integer?T (≤ 10000), denoting the number of test cases.

Each case contains an integer?n (1 ≤ n < 231)
and the name of the player who starts first.

Output

For each case, print the case number and the name of the winning player.

Sample Input

3
1 Alice
2 Alice
3 Bob

Sample Output

Case 1: Bob
Case 2: Alice
Case 3: Alice

题意： Alice和Bob取石子，一开始有n颗石子，每轮游戏开始前确定谁先手，若Alice先手，谁取到最后一个石子谁输，若Bob先手，谁取到最后一个石子谁赢。

分析：?巴什博弈，如果没看出来找找规律也可以做出来。对于取到最后一个石子会赢的情况，如果对方出现n%(m+1)=0这种情况，则己方必胜，对于取到最后一个石子会输的情况，相等于取到第n-1个石子的人会赢，转化为上一种情况，如果对方出现(n-1)%(m+1)=0这种情况，则己方必胜。其中m是可选择范围[1, m]。

具体代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

signed main()
{
	int T;
	cin >> T;
	for(int i = 1; i <= T; i++)
	{
		printf("Case %d: ", i);
		int n;
		char name[10];
		scanf("%d%s", &n, name);
		if(*name == 'A')
		{
			//轮到Alice时剩2或3或5或6颗必胜，剩1或4或7颗必输 
			if((n-1) % 3 == 0)
				puts("Bob");
			else
				puts("Alice");
		}
		else
		{
			//轮到Bob时如果剩3或6或9颗必输，剩1或2或4或5颗必胜 
			if(n % 3 == 0)
				puts("Alice");
			else
				puts("Bob"); 
		}
	} 
    return 0;
}