#include <bits/stdc++.h>
#include "prison.h"
using namespace std;
int n = 5000;
int real_N;
int trit(int x,int pos)
{
for (int i = 1; i <= pos; i++)
x /= 3;
return x % 3;
}
vector<vector<int>> get_real_ans(vector<vector<int>> ans)
{
vector<vector<int>> real_ans;
real_ans.resize(ans.size());
for (int i = 0; i < ans.size(); i++)
for (int j = 0; j < real_N + 1; j++)
real_ans[i].push_back(ans[i][j]);
return real_ans;
}
vector<vector<int>> devise_strategy(int N)
{
real_N = N;
vector<vector<int>>ans;
ans.resize(25);
for (int i = 0; i < 25; i++)
ans[i].resize(n + 1);
ans[0][0] = 0;
for (int i = 1; i <= n; i++)
ans[0][i] = 1 + trit(i,7);
for (int i = 1; i <= 24; i++)
{
if (((i - 1) / 3) % 2 == 0)
{
///primul numar e (i - 1) % 3, ma uit la al doilea
ans[i][0] = 1;
for (int j = 1; j <= n; j++)
{
int poztrit = 7 - (i - 1) / 3;
int curtrit = trit(j,poztrit);
if (curtrit != (i - 1) % 3)
{
if (curtrit > (i - 1) % 3)
ans[i][j] = -1;
else
ans[i][j] = -2;
}
else
ans[i][j] = ((i - 1) / 3) * 3 + 3 + 1 + trit(j,poztrit - 1);
}
}
else
{
ans[i][0] = 0;
for (int j = 1; j <= n; j++)
{
int poztrit = 7 - (i - 1) / 3;
int curtrit = trit(j,poztrit);
if (curtrit != (i - 1) % 3)
{
if (curtrit > (i - 1) % 3)
ans[i][j] = -2;
else
ans[i][j] = -1;
}
else
ans[i][j] = ((i - 1) / 3) * 3 + 3 + 1 + trit(j,poztrit - 1);
}
}
if (i >= 22)
for (int j = 1; j <= n; j++)
if (ans[i][j] >= 0)
ans[i][j] = -1;
}
vector<vector<int>> real_ans = get_real_ans(ans);
return real_ans;
}
/**
Idee sqrt -> Iau un B = sqrt(N), intreb primul numar si raspund cu 1 + x / B, intreb al doilea cand vad ceva sub N / B si daca da alt x / B raspund
-> Daca da acelasi x / B, pun un N / B + 2 si il rog pe primul sa intrebe x % B punand N / B + 3 + x % B, la care al doilea vede si compara x % B
Asta foloseste gen 2sqrt(N), 10p
**/
/**
Idee biti -> Vad 0, intreb de primul numar si ii pun 1 + primul bit. Al doilea vede asta si compara primii biti. La egalitate, scrie 3 si se repeta procesul
-> Candva, vor da bitii diferiti
Asta foloseste 3logN = 39, 26.5p
**/
/**
Idee biti based -> Vad 0, intreb primul numar si ii scriu 1 + primul bit. Al doilea citeste 1 / 2, compara cu primul bit din al doilea numar
-> Daca e diferit de primul bit din primul numar, e gata, altfel scrie 3 / 4 reprezentand al doilea bit din al doilea numar
Asta foloseste 2logN = 26, 42p
**/
/**
Optimizari:
-> Pot folosi baza 3 si fac x = 3log3(N) = 3 * 8 = 24, 65p
-> Pot sa tai putin de la ultimul bit cu o chestie actually cute: cand primul intreaba, daca e 0 sau 2 atunci clar stiu rez (fiind diferite), altfel pun +1
-> Cu ultima optimizare fac x = 3log3(N) - 3 + 1 = 22, 80p
**/
