#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
map<array<int,2>,int>mp;
map<int,array<int,2>>rev;
int x = 22;
void pre(){
int cn = 1;
mp[{8,0}]=0;
rev[0]={8,0};
for(int i = 0;i<8;i++){
mp[{i,1}]=cn;
rev[cn++]={i,1};
if(i==0){
continue;
}
mp[{i,0}]=cn;
rev[cn++]={i,0};
mp[{i,2}]=cn;
rev[cn++]={i,2};
}
}
string base3(int n){
string s = "";
while(n){
s+=to_string(n%3);
n/=3;
}
while(s.size()<8){
s+="0";
}
return s;
}
int ret(array<int,2>a, int val){
if(val==0){
if(a[0]%2){
return 0;
}
return 1;
}
string vals = base3(val);
int v = vals[a[0]]-'0';
if(v>a[1]&&a[0]!=8){
//this one is greater
if(a[0]%2){
return -2;
}
else{
return -1;
}
}
else if(v<a[1]&&a[0]!=8){
if(a[0]%2){
return -1;
}
else{
return -2;
}
}
else{
//equal
if(a[0]==1){
if(vals[a[0]-1]-'0'==2){
return -2;
}
if(vals[a[0]-1]-'0'==0){
return -1;
}
}
return mp[{a[0]-1,vals[a[0]-1]-'0'}];
}
}
vector<vector<int>> devise_strategy(int n) {
pre();
vector<vector<int>>s(x+1, vector<int>(n+1));
for(int i = 0;i<=x;i++){
for(int j = 0;j<=n;j++){
s[i][j]=ret(rev[i],j);
}
}
return s;
}
