#include "prison.h"
#include <cmath>
#include <cassert>
#include <cstdio>
#include <string>
#include <vector>
#include <iostream>
using namespace std;
static constexpr int kNumPrisoners = 500;
vector<vector<int>> devise_strategy(int N){
int x = 30;
vector<vector<int>> strat(x + 1, vector<int>(N+1));
// base 3;
for(int i = 0; i <= x; i ++){
if(i % 2){
strat[i][0] = 0;
}
else{
strat[i][0] = 1;
}
if(i == 0){
strat[i][0] = 0;
int bit = 7;
for(int j = 1; j <= N; j ++){
int bits = (int)(j / pow(3, bit + 1)) % (int)pow(3, bit);
strat[i][j] = 1 + bits * 8 + bit;
}
}
else if(i % 2){
int sett = (i >= 9) + (i >= 17);
int bit = i - 1 - sett * 8;
for(int j = 1; j <= N; j ++){
int bits = j % (int)pow(3, bit + 1) / (int)pow(3, bit);
if(sett > bits){
strat[i][j] = -1;
}
else if(bits > sett){
strat[i][j] = -2;
}
else{
bits = j % (int)pow(3, bit) / (int)pow(3, (bit?bit-1:0));
strat[i][j] = bits * 8 + bit;
}
}
}
else if(i % 2 == 0){
int sett = (i >= 9) + (i >= 17);
int bit = i - 1 - sett * 8;
for(int j = 1; j <= N; j ++){
int bits = j % (int)pow(3, bit + 1) / (int)pow(3, bit);
if(sett > bits){
strat[i][j] = -2;
}
else if(bits > sett){
strat[i][j] = -1;
}
else{
bits = j % (int)pow(3, bit) / (int)pow(3, (bit ? bit-1 : 0));
strat[i][j] = bits * 8 + bit;
}
}
}
}
return strat;
}
