#include "prison.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
typedef long long llong;
const int MAXN = 5000 + 10;
const int INF = 1e9;
int power[MAXN];
inline int getBit(int num, int bit)
{
return (num / power[bit]) % 3;
}
inline int encode(int bit, int val)
{
if (bit == 0) return 1;
return 3 * bit + val - 1;
}
std::vector <std::vector <int>> s;
std::vector <std::vector <int>> devise_strategy(int n)
{
power[0] = 1;
for (int i = 1 ; i <= 8 ; ++i)
{
power[i] = power[i - 1] * 3;
}
s.resize(23);
s[0].resize(n + 1, 0);
for (int x = 1 ; x <= n ; ++x)
{
s[0][x] = encode(7, getBit(x, 7));
}
for (int bit = 0 ; bit <= 7 ; ++bit)
{
for (int val = 0 ; val <= 2 ; ++val)
{
s[encode(bit, val)].resize(n + 1, 0);
s[encode(bit, val)][0] = (bit & 1);
for (int money = 1 ; money <= n ; ++money)
{
if (getBit(money, bit) < val)
{
if (bit & 1) s[encode(bit, val)][money] = -2;
else s[encode(bit, val)][money] = -1;
continue;
}
if (getBit(money, bit) > val)
{
if (bit & 1) s[encode(bit, val)][money] = -1;
else s[encode(bit, val)][money] = -2;
continue;
}
if (bit == 0) continue;
if (bit == 1)
{
if (getBit(money, bit - 1) == 0)
{
if (bit & 1) s[encode(bit, val)][money] = -1;
s[encode(bit, val)][money] = -2;
continue;
}
if (getBit(money, bit - 1) == 2)
{
if (bit & 1) s[encode(bit, val)][money] = -2;
s[encode(bit, val)][money] = -1;
continue;
}
}
s[encode(bit, val)][money] = encode(bit - 1, getBit(money, bit - 1));
}
}
}
return s;
}
