#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
using vpii = vector<pii>;
using vvpii = vector<vpii>;
#define sz(x) int(x.size())
const int lg = 8;
vi pow3 = vi(1 + lg);
int getdigit(int i, int d)
{
if(d < 0)
return 0;
return (i / pow3[d]) % 3;
}
vvi devise_strategy(int N)
{
pow3[0] = 1;
for(int e = 1; e <= lg; e++)
pow3[e] = 3 * pow3[e-1];
vvi s(3*lg+1, vi(1+N, -1));
s[0][0] = 0;
for(int i = 1; i <= N; i++)
{
s[0][i] = 1 + getdigit(i, lg-1);
}
for(int p = 0; p < lg; p++)
{
int b = lg-1 - p;
if(p % 2 == 0) //even bit, check B
{
s[3*p + 1][0] = 1;
s[3*p + 2][0] = 1;
s[3*p + 3][0] = 1;
for(int i = 1; i <= N; i++)
{
int cd = getdigit(i, b); //current digit
for(int wd = 0; wd <= 2; wd++) //whiteboard digit
{
if(cd < wd)
{
s[3*p + 1 + wd][i] = -2;
}
else if(wd < cd)
{
s[3*p + 1 + wd][i] = -1;
}
else
s[3*p + 1 + wd][i] = 3*(p+1) + 1 + getdigit(i, b-1);
}
}
}
else //odd bit, check A
{
s[3*p + 1][0] = 0;
s[3*p + 2][0] = 0;
s[3*p + 3][0] = 0;
for(int i = 1; i <= N; i++)
{
int cd = getdigit(i, b); //current digit
for(int wd = 0; wd <= 2; wd++) //whiteboard digit
{
if(cd < wd)
{
s[3*p + 1 + wd][i] = -1;
}
else if(wd < cd)
{
s[3*p + 1 + wd][i] = -2;
}
else
s[3*p + 1 + wd][i] = 3*(p+1) + 1 + getdigit(i, b-1);
}
}
}
}
int x = sz(s) - 1;
for(int i = 0; i < sz(s); i++)
for(int j = 0; j <= N; j++)
if(s[i][j] > x)
s[i][j] = -1;
// for(int i = 0; i <= x; i++)
// {
// for(int j = 0; j <= N; j++)
// {
// cerr << i << ' ' << j << " : " << s[i][j] << '\n';
// }
// }
return s;
}
