#include "bits/stdc++.h"
using namespace std;
int p3[] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561};
// base 3
int get_bit(int n, int bit) {
return (n % p3[bit + 1]) / p3[bit];
}
const int NBIT = 8; // 3**8 > 5000
int encode(int b, int t) {
if (b < 0) return 0;
return 1 + b * 3 + t;
}
std::vector<std::vector<int>> devise_strategy(int n) {
const int NSTATE = NBIT * 3 + 1;
std::vector<std::vector<int>> res(NSTATE, std::vector<int> (n+1, 0));
// 0
{
res[0][0] = 0;
for (int i = 1; i <= n; ++i) {
int t = get_bit(i, NBIT - 1);
res[0][i] = encode(NBIT - 1, t);
}
}
// compare each digit in base 3
for (int bit = NBIT - 1; bit >= 0; --bit) {
for (int t = 0; t < 3; ++t) {
int state = encode(bit, t);
int cur = bit % 2;
int last = 1 - cur;
// 7 -> read 1
// 6 -> read 0
res[state][0] = cur;
for (int i = 1; i <= n; ++i) {
int cur_bit = get_bit(i, bit);
if (t < cur_bit) res[state][i] = -1 - last;
else if (t > cur_bit) res[state][i] = -1 - cur;
else {
// 2 digits are equal -> we continue to next digit
// to improve, we read next digit of current number and store it directly
// (alternating 2 numbers)
if (bit == 0) res[state][i] = 0;
else res[state][i] = encode(bit - 1, get_bit(i, bit - 1));
}
}
}
}
return res;
}
