#include "prison.h"
#include <vector>
#include <iostream>
using namespace std;
int get_bit(int val, int bit) {
while (bit-- > 0) val /= 3;
return val % 3;
}
int ans(bool low, bool t) {
if (!low) t = !t;
// B A
return t ? -2 : -1;
}
int handle(int i, int j) {
// 0 -> 0
// 1-3 -> 1
// 4-6 -> 2
int steps = (i + 2) / 3;
bool t = steps % 2;
if (j == 0) return t;
int cmp = i == 0 ? -1 : (i - 1) % 3;
int bit = i == 0 ? -1 : get_bit(j, 8 - steps);
if (i == 22) cmp = 1;
if (cmp == -1) {
return 1 + get_bit(j, 8 - steps - 1);
} else if (bit < cmp) {
return ans(1, t);
} else if (bit > cmp) {
return ans(0, t);
} else {
if (steps == 7) {
int nxt_bit = get_bit(j, 0);
if (nxt_bit == 0) return ans(1, t);
else if (nxt_bit == 2) return ans(0, t);
else return 22;
}
return steps * 3 + 1 + get_bit(j, 8 - steps - 1);
}
}
vector<vector<int>> devise_strategy(int N) {
vector<vector<int>> res;
int mx = 22;
for (int i = 0; i <= mx; ++i) {
vector<int> cur;
for (int j = 0; j <= N; ++j) {
cur.push_back(min(handle(i, j), mx));
}
res.push_back(cur);
}
/*int row = 0;
for (auto g : res) {
cout << row++ << ": ";
for (int x : g) cout << x << " ";
cout << endl;
}*/
return res;
}
