#include <bits/stdc++.h>
using namespace std;
const int N = 5000;
int n, last = 0;
int ans[N + 5][N + 5];
int b3(int x, int bit)
{
while (bit --)
x /= 3;
return x % 3;
}
void build(int pos, int bit, int care, int other, int nxt) //schimbare la baza 3 now
{
last = max(last, pos);
if (pos == 0)
{
ans[0][0] = 0;
for (int i = 1; i <= n; i ++)
ans[0][i] = 1 + b3(i, bit);
build (1, 7, 1, 0, 4);
build (2, 7, 1, 1, 4);
build (3, 7, 1, 2, 4);
return;
}
else if (bit == 0)
{
ans[pos][0] = care;
for (int i = 1; i <= n; i ++)
{
int x = b3(i, bit);
if (x == 0)
ans[pos][i] = - care - 1;
else
ans[pos][i] = - (1 - care) - 1;
}
return;
}
else
{
ans[pos][0] = care;
for (int i = 1; i <= n; i ++)
{
if (b3(i, bit) > other) //castiga other
ans[pos][i] = - (1 - care) - 1;
else if (b3(i, bit) < other)
ans[pos][i] = - care - 1;
else if (bit == 1)
{
int x = b3(i, bit - 1);
if (x == 0) //castig eu
ans[pos][i] = - care - 1;
else if (x == 2)
ans[pos][i] = - (1 - care) - 1;
else
ans[pos][i] = nxt;
}
else
ans[pos][i] = nxt + b3(i, bit - 1);
}
if (other == 1 && bit > 1)
{
build (nxt, bit - 1, 1 - care, 0, nxt + 3);
build (nxt + 1, bit - 1, 1 - care, 1, nxt + 3);
build (nxt + 2, bit - 1, 1 - care, 2, nxt + 3);
}
else if (bit == 1)
build (nxt, 0, 1 - care, 1, nxt);
}
}
vector<vector<int>> devise_strategy(int _n)
{
n = _n;
build (0, 7, 0, 0, 0);
vector<vector<int>> strat(last + 1, vector<int>(n + 1));
for (int i = 0; i <= last; i ++)
for (int j = 0; j <= n; j ++)
strat[i][j] = ans[i][j];
return strat;
}
/*
int main()
{
int n, a, b, tabla = 0;
cin >> n >> a >> b;
auto st = devise_strategy(n);
while (1)
{
cout << tabla << '\n';
int ntabla = 0;
if (st[tabla][0] == 0) //citeste din a
ntabla = st[tabla][a];
else
ntabla = st[tabla][b];
if (ntabla < 0)
{
cout << -ntabla << '\n';
exit(0);
}
tabla = ntabla;
}
}
*/
