#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
int get_num(int digit, int pos) { return 3 * pos + digit + 1; }
string base3(int n) {
string s;
while (n) {
s += (n % 3) + '0';
n /= 3;
}
while (s.size() < 8) s += '0';
reverse(s.begin(), s.end());
return s;
}
int whichBag(int pos, int ifA, int ifB){
if(pos%2) return ifA;
return ifB;
}
vector<vector<int>> devise_strategy(int n) {
vector<vector<int>> strategy(27, vector<int>(n+1));
for(int pos = 0; pos < 8; pos++){
for(int digit = 0; digit < 3; digit++){
int num = get_num(digit, pos);
if(num >= 0) strategy[num][0] = whichBag(pos, 0, 1);
}
}
for(int i=1;i<=n;i++){
string cur = base3(i);
strategy[0][i] = get_num(cur[0]-'0', 0);
for(int pos = 0; pos < 8; pos++){
int thisDigit = cur[pos] - '0';
for(int digit = 0; digit < 3; digit++){
int num = get_num(digit, pos);
if(num >= 0){
if(thisDigit > digit) strategy[num][i] = whichBag(pos, -2, -1);
else if(thisDigit < digit) strategy[num][i] = whichBag(pos, -1, -2);
else if(thisDigit == digit && pos != 7) strategy[num][i] = get_num(cur[pos+1] - '0', pos+1);
}
}
}
}
// for(auto& v : strategy){
// for(auto& x : v) cout << x << " ";
// cout << endl;
// }
return strategy;
}
