Nim game:
It is an ancient game.Charles Boute discovered the trick behind the game strategy to win obviously.
The idea is to figure out the current state of the stones of all the piles. If it is in the zero state then there is no way we can make a move to put the state again in zero state.
Here is a bit scenario explanation from here,
Let’s start by playing with some examples. Suppose the two players are called A and B, and suppose that A goes first. Suppose there are two heaps with a coin each. Then clearly, player B is guaranteed to win: A has to take one of the two coins, leaving B to take the last one.
Now suppose that there are two heaps, one of which contains two coins and the other one. Now player A has a winning strategy: take one of the coins in the two-coin heap. This leaves two heaps with a coin each and B to go next. And as we saw in the previous example, this means that A will win.
Let’s do one more: suppose that there are two heaps with two coins each. Now player B has a winning strategy. If A takes an entire heap, then B should take the remaining heap and win. If A takes only one coin of one of the heaps, then we are in the same situation as in the previous example, with B to go first. Therefore, B is guaranteed to win if she takes one coin from the two-coin heap.
Solution:
To solve this we need to find the initial state of the stone files if it is in zero state or not. This can be done by doing bitwise XOR of the stones of all the piles. This bit wise XOR calculation is also known as “nimber” addition.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
#include <stdio.h> #include <iostream> using namespace std; int main() { int n,a,ans; while(scanf("%d",&n),n!=0) { cin>>ans; for(int i=1;i<n;i++) { cin>>a; ans=ans^a; } if(ans==0) cout<<"No\n"; else cout<<"Yes\n"; } return 0; } |