WUSTOJ 1254: 盒子游戏

参考博客

叶剑飞Victor的博客
 盒子游戏——爱程序网
原理是从上面博客看的，我另外补充了几幅图，方便理解

Description

有两个相同的盒子，其中一个装了n个球，另一个装了一个球。Alice和Bob发明了一个游戏，规则如下：Alice和Bob轮流操作，Alice先操作。每次操作时，游戏者先看看哪个盒子里的球的数目比较少，然后清空这个盒子（盒子里的球直接扔掉），然后把另一个盒子里的球拿一些到这个盒子中，使得两个盒子都至少有一个球。如果一个游戏者无法进行操作，他（她）就输了。下图是一个典型的游戏：
1254
面对两个各装一个球的盒子，Bob无法继续操作，因此Alice获胜。你的任务是找出谁会获胜。假定两人都很聪明，总是采取最优策略。

Input

输入最多包含300组测试数据。每组数据仅一行，包含一个整数n（2<=n<=10^9）。输入结束标志为n=0。

Output

对于每组数据，输出胜者的名字。

Sample Input

Sample Output

Alice
Bob
Alice

题目分析

n=2时，Alice(A)拿完球后，只能得到（1,1）这种情况，结果A赢。

n=3时，A先拿，只能得到（2,1），Bob(B)再拿，只能得到（1,1），结果B赢。

n=4时，A一定会将球分成（3,1），B只能将球分成（2,1），A只能将球分成（1,1），结果A赢。
n=5时，A一定会将球分成（3,2），B只能将球分成（2,1），A只能将球分成（1,1），结果A赢。
在这里插入图片描述 n=6时，A一定会将球分成（3,3），B只能将球分成（2,1），A只能将球分成（1,1），结果A赢。
n=7时，无论A将球分成多少，B一定会将球分成（3，k）(k=1,2,3)，A只能将球分成（2,1），B只能将球分成（1,1），结果B赢。（WPS流程图有限制。。。不规范的是我用图片编辑补充的。）

结论1：当球的个数为（m,n）且满足1<=n<=m，m=2^k-1（k=1,2,3,4,…）时，当前拿球的人一定会输。

由于Alice先拿球，我们可以这么理解，如果Alice不能将球分成结论1的情况，那么Bob一定会将球分成结论1的情况，从而导致自己输掉。

由于Alice先拿球，可以进一步将结论分成2个：

1、球的个数为结论1所示，Alice一定会输；
2、球的个数不为结论1所示，Alice都可以将球分成结论1所示，Alice一定会赢。

这里有必要说明一点，拿球结果只和球较多的那部分有关，较少的部分最终都会被扔掉，不必考虑。不明白就多看几遍上面的图并自行体会。

这里我们只需要证明第1条（即结论1）成立，第2条自然也就成立。下面就用数学归纳法来证明第1条是否成立：

解：
第一步，当k₁=1时，盒子状态为（1，1），当前是Alice拿，因此Alice输；
第二步，当k₂=k₁+1时，盒子状态为（3，1），当前是Alice拿，因此Alice输；
第三步，令k=e时，球的状态为（2^e-1，1）时，满足结论1，当前是Alice拿，因此Alice输；
当k=e+1时，球的状态为（2^e+1-1，1），
Alice只能分成（m，n），且1<=n<=m，m+n=2^e+1-1，
那么m的范围是[2^e,2^e+1-2]，（与此对应的n的范围是[2^e-1,1]），
因此可以看出m是大于k=e时的球个数2^e-1的
也就是说，Alice是不可能将球的个数分成（2^e-1，1）的，接下来Bob肯定将球分成（2^e-1,1）从而让Alice拿，也就是让Alice输。
因此当k=e时，能够使k=e+1满足结论1，因此，结论1成立。结论得证。

代码

分析：当n=2^k-1时，n的二进制是前面一串0，最后k个1，
因此n&1只有2种情况1和0，如果是1，将n右移1位；如果是0，退出右移循环。
此时判断n是否等于0，等于0说明n=2^k-1，那么Alice输
不等于0，说明n最后一位的左边还有1，而最后一位是0，显然与开头说的最后k个1中的最后相矛盾，那么Alice赢。

// 这是参考博客的第一个的方法
// 提交用时：349ms
import java.util.Scanner;

public class Main {

	private Scanner sc;
	private int n;
	
	public Main() {
		sc = new Scanner(System.in);
		n = sc.nextInt();
		while(0 != n) {
			while((n & 1) == 1) {
				n >>= 1;
			}
			if(0 == n) {
				System.out.println("Bob");
			} else {
				System.out.println("Alice");
			}
			n = sc.nextInt();
		}
		sc.close();
	}
	
	public static void main(String[] args) {
		new Main();
	}

}

分析：既然我们已经知道了Bob赢时的n值，那为何我们不将这些n值先算出来呢，再同输入的值相比较，这样对于数据较多（此题明确说了最多300组数据）时，肯定会缩短计算时间的。

// 这是参考博客的第二个的方法
// 提交用时：256ms
import java.util.Scanner;

public class Main {

	private Scanner sc;
	private int n, i;
	private int[] bob;	// 使得Bob赢的n值
	
	public Main() {
		sc = new Scanner(System.in);
		bob = new int[32];
		bob[0] = 1;
		for(i = 1; i <= 31; i++) {
			bob[i] = bob[i - 1] * 2 + 1;
		}
		n = sc.nextInt();
		while(0 != n) {
			for(i = 1; i <= 31; i++) {
				if(n == bob[i]) {
					System.out.println("Bob");
					break;
				} else if(n < bob[i]) {
					System.out.println("Alice");
					break;
				}
			}
			n = sc.nextInt();
		}
		sc.close();
	}

	public static void main(String[] args) {
		new Main();
	}

}

1254: 盒子游戏（Java）