#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
#define bv(x, i) (((x) & (1 << (i))) ? 1 : 0)
#define trit(x, i) (((x) / static_cast<int>(std::pow(3, (i)))) % 3)
#define p3(p) int(pow(3, p))
using vi = vector<int>;
using vvi = vector<vi>;
const int STATES = 23;
int transition(int current, int bagValue) {
if (current == 0) {
return trit(bagValue, 7) + 1;
} else if (current == 21) {
if (trit(bagValue, 1) < 2) return -2;
if (trit(bagValue, 0) == 1) return 22;
return trit(bagValue, 0) == 2 ? -1 : -2;
} else if (current == 20) {
if (trit(bagValue, 1) > 1) return -1;
else if (trit(bagValue, 1) < 1) return -2;
if (trit(bagValue, 0) == 1) return 22;
return trit(bagValue, 0) == 2 ? -1 : -2;
} else if (current == 19) {
if (trit(bagValue, 1) > 0) return -1;
if (trit(bagValue, 0) == 1) return 22;
return trit(bagValue, 0) == 2 ? -1 : -2;
}
else if (current == 22) {
return trit(bagValue, 0) > 1 ? -2 : -1;
} else if (current == 24) {
return -1;
} else if (current == 23) {
return trit(bagValue, 0) > 1 ? -2 : -1;
}
// else if (current == 24) {
// if (bagValue & (1 << 1)) return -2;
// return bagValue & (1 << 0) ? -2 : -1;
// } else if (current == 23) {
// if (bagValue & (1 << 1)) return bagValue & (1 << 0) ? -2 : -1;
// return -1;
// }
int bit = 8 - ((current + 2) / 3);
int pos = (current - 1) % 3;
bool isa = bit % 2 == 0;
if (bit < 0) return -1;
if (trit(bagValue, bit) == pos) {
// cout << "cold: " << current << " cbit: " << bit << "\n";
current = ((8 - bit) - 1) * 3 + 1;
// cout << current << "\n";
int toret = -1;
if (trit(bagValue, bit - 1) == 0) toret = current + 3;
if (trit(bagValue, bit - 1) == 1) toret = current + 4;
if (trit(bagValue, bit - 1) == 2) toret = current + 5;
if (toret >= 22) toret = 22;
return toret;
} else {
if (isa) {
return trit(bagValue, bit) > pos ? -2 : -1;
} else {
return trit(bagValue, bit) > pos ? -1 : -2;
}
}
return -1;
}
vi used(32, 0);
int test_strategy(int a, int b, vvi &strategy) {
int cnum = 0;
for (int i = 0; i < 500; i++) {
used[cnum]++;
int choose = strategy[cnum][0];
if (strategy[cnum][choose ? b : a] < 0) {
return -strategy[cnum][choose ? b : a];
} else {
cnum = strategy[cnum][choose ? b : a];
}
}
return 0;
}
vvi devise_strategy(int N) {
vvi s(STATES, vi(N+1, 0));
for (int i = 0; i < STATES; i++) {
// State cur = states[i];
int bit = 8 - ((i + 2) / 3);
s[i][0] = bit % 2 == 0 ? 0 : 1;
for (int j = 1; j <= N; j++) {
s[i][j] = transition(i, j);
if (s[i][j] < -2 || s[i][j] >= STATES) s[i][j] = -1;
}
}
// for (int i = 1; i <= 5000; i++) {
// for (int j = 1; j <= 5000; j++) {
// if (i == j) continue;
// int ans = test_strategy(i, j, s);
// if (ans != (i < j ? 1 : 2)) {
// cout << "Fails on: " << i << ", " << j << "\n";
// break;
// }
// }
// }
// vi bits(STATES); iota(bits.begin(), bits.end(), 0);
// sort(bits.begin(), bits.end(), [&](const auto &a, const auto &b) {return used[a] < used[b];});
// for (int i = 0; i < STATES; i++) {
// cout << "Used state " << bits[i] << " " << used[bits[i]] << " times\n";
// }
// int mstate = 0; for (int i = 0; i < used.size(); i++) if (used[i] > 0) mstate = i;
// double score = 10.0F;
// if (40 <= mstate && mstate <= 60) {
// score += 20;
// } else if (26 <= mstate && mstate <= 39) {
// score += 25 + 1.5 * (40 - mstate);
// } else if (24 <= mstate && mstate <= 25) {
// score += 50 + 5 * (25 - mstate);
// } else if (mstate == 23) {
// score += 62;
// } else {
// score += 70 + 10 * (22 - mstate);
// }
// cout << "Max X: " << mstate << " Solution scores: " << score << " / 100\n";
return s;
}
