#include "prison.h"
#include <vector>
#include <map>
#include <iostream>
#include <cassert>
using namespace std;
using VI = vector<int>;
using VVI = vector<VI>;
using II = pair<int,int>;
enum Result {
A_IS_SMALLER = -1, B_IS_SMALLER = -2
};
std::vector<std::vector<int>> devise_strategy(int N) {
// map of (pos, digit) => x
map<II,int> PD_to_x;
vector<II> x_to_PD = { II(-1,-1) };
for (int pos = 0; pos <= 8; ++pos) {
for (int dig = 0; dig <= 2; ++dig) {
II pd(pos, dig);
int x = x_to_PD.size();
x_to_PD.push_back(pd);
PD_to_x[pd] = x;
}
}
int M = int(x_to_PD.size())-1;
// cerr << "max x = " << M << endl;
vector<int> P3 = {1};
for (int k = 1; k <= 8; ++k)
P3.push_back(P3.back() * 3);
assert(P3.back() >= 5000);
VVI ret(M + 1, VI(N + 1));
ret[0][0] = 0;
ret[0][1] = A_IS_SMALLER;
ret[0][N] = B_IS_SMALLER;
for (int n = 2; n < N; ++n) {
int msd = n / P3[8];
assert(PD_to_x.count(II(0, msd)));
ret[0][n] = PD_to_x[II(0, msd)];
}
for (int x = 1; x <= M; ++x) {
int pos, bdig;
tie(pos, bdig) = x_to_PD[x];
bool inspectA = pos % 2 == 1;
ret[x][0] = inspectA ? 0 : 1;
ret[x][1] = inspectA ? A_IS_SMALLER : B_IS_SMALLER;
ret[x][N] = inspectA ? B_IS_SMALLER : A_IS_SMALLER;
for (int n = 2; n < N; ++n) {
int ndig = (n / P3[8-pos]) % 3;
if (ndig < bdig) {
ret[x][n] = inspectA ? A_IS_SMALLER : B_IS_SMALLER;
}
else if (ndig > bdig) {
ret[x][n] = inspectA ? B_IS_SMALLER : A_IS_SMALLER;
}
else if (pos+1 <= 8) {
ndig = (n / P3[8-(pos+1)]) % 3;
assert(PD_to_x.count(II(pos+1, ndig)));
ret[x][n] = PD_to_x[II(pos+1, ndig)];
}
else {
ret[x][n] = -1;
}
}
}
/*
for (int x = 0; x <= M; ++x) {
int pos, dig;
tie(pos, dig) = x_to_PD[x];
cerr << x << " " << pos << "," << dig << ": ";
for (int n = 0; n <= N; ++n)
cerr << ret[x][n] << ' ';
cerr << endl;
}
*/
return ret;
}
