#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
pair<int, int> reduce(int v, int t) {
// cerr << "reducing " << v << " by " << t << ": ";
v--;
int h = 3 * 3 * 3 * 3 * 3 * 22, a;
for (int i = 0; i < min(t, 5); i++) {
h /= 3;
v %= h;
}
if (t < 5)
a = v / (h / 3);
for (int i = 0; i < min(t - 5, 2); i++) {
if (v == 0 || v == h - 1)
return {v, v == 0 ? -1 : -2};
v--;
h -= 2;
h /= 2;
v %= h;
}
if (t >= 5 && t < 7)
a = v == 0 ? -1 : (v == h - 1 ? -2 : (v - 1) / ((h - 2) / 2));
if (t == 7)
a = v == 0 ? -1 : (v == h - 1 ? -2 : 0);
if (t > 7) {
if (v == 0 || v == h - 1)
return {v, v == 0 ? -1 : -2};
v--;
h -= 2;
a = v == 0 ? -1 : -2;
}
// cerr << v << " " << a << " " << h << "\n";
return {v, a};
}
tuple<int, int, int> pile(int x) {
int p = 0;
int i = 0, j = 0;
if (x)
p ^= 1, j++;
for (i = 0; i < 5 && x > 3; i++, x -= 3, j++)
p ^= 1;
if (i == 5) {
for (i = 0; i < 2 && x > 2; i++, x -= 2, j++)
p ^= 1;
if (i == 2 && x > 1)
i = 0, j++, x--, p ^= 1;
}
return {p, x, j};
}
int undo(int x, int t) {
for (int i = 0; i < min(5, t); i++)
x += 3;
for (int i = 5; i < min(7, t); i++)
x += 2;
if (t == 8)
x++;
return x;
}
int action(int x, int v) {
if (x == 0) {
auto [nv, a] = reduce(v, 0);
if (a < 0)
return a;
return a + 1;
}
auto [p, nx, t] = pile(x);
auto [nv, a] = reduce(v, t - 1);
if (a < 0)
return a ^ p;
if (a + 1 != nx)
return (a + 1 < nx ? -1 : -2) ^ p;
auto [nnv, na] = reduce(v, t);
if (na < 0)
return na ^ p;
return undo(na + 1, t);
}
std::vector<std::vector<int>> devise_strategy(int N) {
vector<vector<int>> s(21, vector<int>(N + 1));
for (int x = 0; x < 21; x++) {
auto [p, nx, t] = pile(x);
s[x][0] = p;
for (int v = 1; v <= N; v++)
s[x][v] = action(x, v);
}
return s;
}
