#include "prison.h"
#include <vector>
using namespace std;
vector<vector<int>> V;
void f(int x, int l, int r, int t)
{
if(l + 1 >= r) return;
for(int y = x; y <= 20; ++y) V[y][l] = -1 - V[y][0], V[y][r - 1] = -2 + V[y][0];
++l; --r;
if(l == r) return;
int c;
if(t == 19) c = 2;
else c = 3;
for(int i = 0; i < c; ++i)
{
int s = ((c - i) * l + i * r) / c, e = ((c - i - 1) * l + (i + 1) * r) / c;
for(int j = s; j < e; ++j) V[x][j] = t + i;
for(int j = l; j < s; ++j) V[t + i][j] = -2 + V[x][0];
for(int j = e; j < r; ++j) V[t + i][j] = -1 - V[x][0];
f(t + i, s, e, t + c);
}
}
vector<vector<int>> devise_strategy(int N)
{
int x = 20;
V = vector<vector<int>>(x + 1, vector<int>(N + 1));
V[0][0] = 0;
V[1][0] = 1;
V[2][0] = 1;
V[3][0] = 1;
V[4][0] = 0;
V[5][0] = 0;
V[6][0] = 0;
V[7][0] = 1;
V[8][0] = 1;
V[9][0] = 1;
V[10][0] = 0;
V[11][0] = 0;
V[12][0] = 0;
V[13][0] = 1;
V[14][0] = 1;
V[15][0] = 1;
V[16][0] = 0;
V[17][0] = 0;
V[18][0] = 0;
V[19][0] = 1;
V[20][0] = 1;
f(0, 1, N + 1, 1);
return V;
}
