#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int base = 3;
int getKth(int x,int k){
while(k > 0){
x /= base;
k--;
}
return x % base;
}
std::vector<std::vector<int>> devise_strategy(int N) {
vector<vector<int>> strategy(25,vector<int>(N+1,0));
strategy[0][0] = 0;
for(int i = 1; i <= N; i++){
strategy[0][i] = (base*7 + getKth(i,7)-1);
}
strategy[0][1] = -1;
strategy[0][N] = -2;
for(int i = 1; i <= 24; i++){
int cur_pos = (i+1)/3;
int bt = (i+1) % 3;
strategy[i][0] = cur_pos % 2;
if(i == 1){
for(int j = 1; j <= N; j++){
if(getKth(j,0) == 0)
strategy[i][j] = -(strategy[i][0])-1;
else if(getKth(j,0) == 2)
strategy[i][j] = -(strategy[i][0]^1)-1;
else
strategy[i][j] = 0;
}
continue;
}
for(int j = 1; j <= N; j++){
int bt2 = getKth(j,cur_pos);
// cerr << j << " " << bt2 << "\n";
if(bt2 > bt){
strategy[i][j] = -(strategy[i][0]^1)-1; /// cur is >
} else if(bt2 < bt){
strategy[i][j] = -(strategy[i][0])-1; /// cur is <
} else {
if(cur_pos > 0){
if(cur_pos > 1)
strategy[i][j] = (base * (cur_pos-1) + getKth(j,cur_pos-1)-1);
else {
/// 0,1,2
if(getKth(j,0) == 2)
strategy[i][j] = -(strategy[i][0]^1)-1;
else if(getKth(j,0) == 0)
strategy[i][j] = -(strategy[i][0])-1;
else
strategy[i][j] = 1;
}
}
else
strategy[i][j] = -1; /// cannot be
}
}
}
return strategy;
}
/**
5000
1 2
1 3
2 1
2 3
3 1
3 2
4096 4097
-1
**/
