#include "prison.h"
#include <vector>
std::vector<std::vector<int>> devise_strategy(int N) {
using namespace std;
vector<vector<int>> strat(21, vector<int>(N + 1, 0));
vector<int> p3(8);
p3[0] = 1;
p3[1] = 4;
p3[2] = 8;
for (int i = 3; i < 8; ++i) {
p3[i] = p3[i - 1]*3;
}
strat[0][0] = 1;
for (int i = 1; i <= N; ++i) {
strat[0][i] = (i / p3[7]) + 1;
}
for (int i = 0; i < 5; ++i) {
strat[1 + 3 * i][0] = strat[2 + 3 * i][0] = strat[3 + 3 * i][0] = i % 2;
for (int j = 1; j <= N; ++j) {
if ((j/p3[7 - i]) % 3 == 0) {
strat[2 + 3*i][j] = strat[3 + 3*i][j] = -1 - i % 2;
strat[1 + 3 * i][j] = 4 + 3*i + (j/p3[6 - i]) % 3;
} else if ((j/p3[7 - i]) % 3 == 1){
strat[3 + 3*i][j] = -1 - i % 2;
strat[1 + 3*i][j] = -2 + i%2;
strat[2 + 3 * i][j] = 4 + 3*i + (j/p3[6 - i]) % 3;
} else {
strat[2 + 3*i][j] = strat[1 + 3*i][j] = -2 + i % 2;
strat[3 + 3 * i][j] = 4 + 3*i + (j/p3[6 - i]) % 3;
}
}
}
strat[16][0] = strat[17][0] = strat[18][0] = 1;
for (int i = 1; i <= N; ++i) {
if ((i/p3[2]) % 3 == 0) {
strat[17][i] = strat[18][i] = -2;
if (i % 4 == 0) {
strat[16][i] = -2;
} else if (i % 4 == 3) {
strat[16][i] = -1;
} else {
strat[16][i] = 19 + i % 2;
}
} else if ((i/p3[2]) % 3 == 1){
strat[18][i] = -2;
strat[16][i] = -1;
if (i % 4 == 0) {
strat[17][i] = -2;
} else if (i % 4 == 3) {
strat[17][i] = -1;
} else {
strat[17][i] = 19 + i % 2;
}
} else {
strat[17][i] = strat[16][i] = -1;
if (i % 4 == 0) {
strat[18][i] = -2;
} else if (i % 4 == 3) {
strat[18][i] = -1;
} else {
strat[18][i] = 19 + i % 2;
}
}
}
strat[19][0] = strat[20][0] = 0;
for (int i = 0; i < N; ++i) {
strat[19][i + 1] = -2 + (((i + 1) % 4) < 1);
strat[20][i + 1] = -2 + (((i + 1) % 4) < 2);
}
return strat;
}
