#include "prison.h"
#include <cmath>
#include <vector>
static int digits, state_count;
struct State {
int digit;
int value;
int variable() const { return digit % 2; }
static State decode(int n) {
n = state_count + 1 - n;
State st;
st.digit = n / 3;
st.value = n % 3;
if (n == 2) {
st.value = 1;
}
return st;
}
int encode() const {
if (digit == 0) {
switch (value) {
case 0:
return -1;
case 1:
return 22;
case 2:
return -2;
}
return -3;
} else {
return state_count + 1 - (digit * 3 + value);
}
}
};
int log(int n, int b) {
int res = 0;
while (n > 0) {
res += 1;
n /= b;
}
res -= 1;
return res;
}
int ipow(int b, int n) {
int res = 1;
while (n--)
res *= b;
return res;
}
int extract(int n, int digit) { return (n / ipow(3, digit)) % 3; }
std::vector<std::vector<int>> devise_strategy(int N) {
digits = log(5000, 3) + 1;
state_count = 23;
std::vector<std::vector<int>> m(state_count);
for (int i = 0; i < state_count; i++) {
std::vector<int> &transitions = m[i];
State st = State::decode(i);
int var = st.variable();
transitions.push_back(!var);
for (int j = 1; j <= N; j++) {
int here = extract(j, st.digit);
if (st.value == here && st.digit > 0) {
State to;
to.digit = st.digit - 1;
to.value = extract(j, to.digit);
transitions.push_back(to.encode());
} else if ((st.value > here) ^ var) {
transitions.push_back(-2);
} else {
transitions.push_back(-1);
}
}
}
return m;
}
