#include <bits/stdc++.h>
#include "prison.h"
using namespace std;
const int x = 39;
vector<int> puissance3;
int bit3(int num, int bit) {
int multAct = bit;
while (num > puissance3[multAct]) multAct++;
while (multAct != bit) {
while (num >= puissance3[multAct])
num -= puissance3[multAct];
multAct--;
}
int reponse = 0;
while (num >= (puissance3[multAct])) {
num -= puissance3[multAct];
reponse++;
}
return reponse;
}
vector<vector<int>> devise_strategy(int N) {
puissance3.resize(9);
puissance3[0] = 1;
for (int i = 1; i <= 8; i++) puissance3[i] = puissance3[i-1]*3;
vector<vector<int>> s(x+1, vector<int>(N+1));
int iBit = 9;
s[0][0] = 0;
for (int A = 1; A <= N; A++) {
s[0][A] = bit3(N, iBit);
}
int idx = 1;
while (iBit >= 0) {
for (int i = 0; i < 3; i++) {
s[idx][0] = ((9-iBit)%2==0?1:0);
int num = 1;
while (num <= N) {
if (bit3(num, iBit) < i) {
s[idx][num] = ((9-iBit)%2==0?-2:-1);
}
if (bit3(num, iBit) == i) {
s[idx][num] = bit3(num, iBit-1)+(9-iBit)*3;
}
if (bit3(num, iBit) > i) {
s[idx][num] = ((9-iBit)%2==0?-1:-2);
}
num++;
}
idx++;
}
iBit--;
}
return s;
}
