Problem 29: Nim Game Variation
Problem Statement: Given n piles of stones, where the i-th pile has a[i] stones, determine the winner of the nim game assuming both players play optimally. Print "First" if the first player wins and "Second" otherwise.
Input
The first line contains an integer n. The second line contains n space-separated integers representing the piles.
Output
Print "First" if the first player wins, otherwise print "Second".
Examples
Input:
3
1 2 3
Output:
Second
Solution Explanation
Method 1: Compute the nim-sum (bitwise XOR) of all pile sizes; if it is nonzero, the first player wins; if it is zero, the second player wins. Method 2: Simulate the game recursively; however, the nim-sum method is more efficient for optimal play.
Solution in C++
#include
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; cin >> n;
int xorSum = 0;
for(int i = 0; i < n; i++){
int x; cin >> x;
xorSum ^= x;
}
cout << (xorSum ? "First" : "Second") << "
";
return 0;
}