PROBLEM LINK:
DIFFICULTY:
MEDIUM
PREREQUISITES:
Game Theory
EXPLANATION:
This one is a typical algorithmic game theory problem. Those who are not familiar with this topic may read this excellent tutorial on topcoder. We can solve this using basic Grundy and NIM theory.
We can pre-compute the grundy values of all possible states the game can be in and then for each test case, xor the corresponding grundy values and if the result is non-zero, Harry ( first player ) wins, else Cent wins.
The first thing to note is, K ≤ N, as allowing a player to remove more Crystals than actually present is useless, so K = minimum(N,K). Let G(N,K) be the grundy value of the state where N stones are present in the pile and at most K Crystals can be removed. If we remove 1 ≤ p ≤ K Crystals in this step, the resultant state is G(N-p,p). We have the following recurrence,
SOLUTIONS:
Solution
#include <iostream>
#include <string>
#include <stream>
#include <iomanip>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <functional>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
using namespace std;
#define MAXN 2022
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t, n, i, j, k, maxx, largest, c, x;
// pre-calculate Grundy number of every possible state
vector<vector<int>> dp(MAXN + 1, vector<int>(MAXN + 1, 0));
for (i = 1; i <= MAXN; i++) { // pile size
unordered_set<int> s;
c = 0; // first missing number;
for (j = 1; j <= min(MAXN, i); j++) { // max # of items to draw
s.insert(dp[i - j][min(i - j, j)]);
while (s.find(c) != s.end()) c++;
dp[i][j] = c;
}
}
cin >> t;
while (t--) {
cin >> n >> maxx;
vector<int> a(n); // pile size
for (i = 0; i < n; i++) cin >> a[i];
// calculate xor of all Grundy numbers
x = 0;
for (i = 0; i < n; i++) {
x ^= dp[a[i]][min(a[i], maxx)];
}
if (x == 0) cout << "Cent\n";
else cout << "Harry\n";
}
return 0;
}