#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
int get_num(int digit, int pos) {
if (pos < 7)
return 3 * pos + digit + 1;
else
return get_num(2, 6) + 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(23, 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);
if (pos == 6) {
if(cur[pos + 1] - '0' == 0){ strategy[num][i] = -2; continue; }
else if(cur[pos + 1] - '0' == 2) { strategy[num][i] = -1; continue; }
}
}
}
}
}
}
// for(auto& v : strategy){
// for(auto& x : v) cout << x << " ";
// cout << endl;
// }
return strategy;
}
