#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
using ii = pair<int, int>;
vector<vector<int> > devise_strategy(int N) {
auto ceil_log = [&](int n, int k) {
int ret = 0, tmp = 1;
while (tmp < n) {
tmp *= k;
ret++;
}
return ret;
};
int min_sf = (int)1e9, base = -1, b = -1;
for (int i = 2; i <= N; i++) {
int j = ceil_log(N - 1, i) - 1;
if (min_sf > (i + 1) * (j + 1) - 1) {
min_sf = (i + 1) * (j + 1) - 1;
base = i;
b = j;
}
}
int x = min_sf;
vector<vector<int> > s(x + 1, vector<int>(N + 1));
auto unpack = [&](int v) {
int b_bit = v / (base + 1), state = v % (base + 1);
return mp(b - b_bit, state);
};
auto pack = [&](int bit, int state) {
int tmp = (b - bit) * (base + 1) + state;
assert(0 <= tmp && tmp <= x);
return tmp;
};
auto get_digit = [&](int num, int pos) {
while (pos--) {
num /= base;
}
return num % base;
};
for (int i = 0; i <= x; i++) {
auto [bit, state] = unpack(i);
if (state == 0) {
s[i][0] = 0;
for (int j = 1; j <= N; j++) {
// find digit at position bit of j
int digit = get_digit(j - 1, bit);
assert(0 <= digit && digit < base);
// write (bit, digit + 1)
s[i][j] = pack(bit, digit + 1);
}
} else {
s[i][0] = 1;
for (int j = 1; j <= N; j++) {
// find digit at position bit of j
int digit = get_digit(j - 1, bit);
if (digit == state - 1) {
if (bit == 0) {
s[i][j] = 0;
} else {
// write (bit - 1, 0)
s[i][j] = pack(bit - 1, 0);
}
} else if (digit > state - 1) {
s[i][j] = -1;
} else {
s[i][j] = -2;
}
}
}
}
return s;
}
