Xtreme 10.0 - Game of Stones
这是 meelo 原创的 IEEEXtreme极限编程大赛题解
Xtreme 10.0 - Game of Stones
题目来源 第10届IEEE极限编程大赛
https://www.hackerrank.com/contests/ieeextreme-challenges/challenges/game-of-stones-1-1
Alice and Bob play a game. The game is turn based: Alice moves first, then Bob, and so on. There are N piles of stones; in every pile there is an odd number of stones. At every turn, the one to play must pick a pile and splits it into 3 piles with an odd number of stones each.
The player who cannot split any pile loses. As this game is too simple for both of them, they decided to play multiple games in parallel. The rules remain the same, but at every turn, the one to play must first pick a game and then split a pile only in that game. The one who loses is the one that can't split any pile in any game, i.e. all the piles in all the games have only 1 stone. Bob still thinks that he is at a disadvantage, since he is the second to move. Your task is to find the winner if both the players play optimally.
Input Format
The input begins with an integer T, giving the number of test cases in the input.
Each testcase begins with an integer G, on a line by itself, giving the number of games to be played in parallel.
The G games are then described in two lines as follows: The first line gives the number of piles in the game, and the second contains the number of stones in each of the piles.
Constraints
1 <= T <= 10
1 <= [Number of piles in all games in a testcase] <= 105
1 <= [Number of stones in a pile] <= 109
Output Format
For each testcase, output the winner, i.e. either Alice or Bob, on a line by itself.
Sample Input
2231 3 523 7151 3 5 7 9
Sample Output
AliceBob
Explanation
The sample input can be annotated as follows:
2 (the number of tests)2 (the number of parallel games for the first test)3 (the number of piles in the first game)1 3 52 (the number of piles in the second game)3 71 (the number of parallel games for the second test)5 (the number of piles)1 3 5 7 9
题目解析
石子个数为N的堆，不论分堆的方式，总共有N/2（整除）次分堆的机会
假设f(N)表示，石子个数为N的堆，总共分堆的次数
可以验证：f(1)=0, f(3)=1, f(5)=2, f(7)=3…… 好心人可以证明一下
所有堆的分堆次数，是每一个堆分堆次数的和
所有游戏的分堆次数，是每一个分堆次数的和
在Alice走第一步之前，如果所有游戏的所有堆的分堆次数为奇数则Alice赢，如果为偶数则Bob赢。
既然游戏的输赢只与和的奇偶性有关，对每一堆的分堆次数二进制末位做一位的二进制加法就好了。
然后，一位的二进制加法可以由异或实现。
程序
C++
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int T;
cin >> T;
for(int t=0; t<T; t++){
int G;
cin >> G;
bool alice = false;
for(int g=0; g<G; g++) {
int P;
cin >> P;
for(int p=0; p<P; p++) {
int n;
cin >> n;
alice ^= (n >> 1) & 1;
}
}
if(alice) {
cout << "Alice" << endl;
}
else {
cout << "Bob" << endl;
}
}
return 0;
}
