INFOMANIA 2023 round 1, educational edition | Bucătăria

Bucătarul John s-a săturat din a mai face ciorbă de legume, a trecut la gătitul ciorbelor cu numere! Pentru a își duce la capăt procesul creativ, a cumpărat un aparat, dar din păcate acesta avea un mecanism avansat de blocare. Astfel, îți cere ajutorul pentru a-l debloca.

Cerință

Există un număr ascuns $X$, care aparține de intervalul $[1, N]$.
Ai voie să pui următorul fel de $query$:

ask(Y)

Dacă $Y > X$, funcția va returna $-1$.
Dacă $Y < X$, funcția va returna $+1$. În plus, față de cazul anterior, numărul X va căpata o nouă valoare ce aparține de același interval, adică $[1, N]$. Fiecare număr din interval are o probabilitate egală să fie ales drept noua valoare a lui $X$.

Altfel, dacă $Y = X$, functia va returna 0, iar dvs. puteti sa incetati din a mai interactiona.
$Y$ trebuie să aparțină de intervalul [1, N]. Altfel, interacțiunea se termină!

Protocolul de interacțiune

Concurentul trebuie să implementeze o funcție:

void solve(int N)

Parametrul N este cel menționat mai sus. Concurentul nu trebuie să implementeze funcția main.
Concurentul poate apela următoarea funcție pentru o interogare:

int ask(int Y)

Funcția se va comporta așa cum este descris în enunț.

Restricții și precizări

• $1 \leq N \leq 10^6$;
• Trebuie să includeți bucataria.h;
• Puteți să vă scrieți codul in bucataria.cpp, completând direct funcția $solve$.
• În cadrul unui test: Fie $best$ numărul de query-uri considerat optim de către comisie și fie $you$ numărul de query-uri pe care le face concurentul.
• Punctarea per test se face după următoarea formulă: $score = \lceil {testPoints \cdot min(\frac{best + error}{you}, 1)} \rceil$, unde $testPoints$ reprezintă numărul de puncte corespunzător respectivului test, iar $1 \leq error \leq 20$ este o eroare de bun simț pe care o permitem programului vostru, ca punctajul maxim să poată fi atins.

Exemplu

N = 10, X = 5

concurent: ask(3); comisia: +1,X=4
concurent: ask(5); comisia: -1
concurent: ask(4); comisia: 0

interacțiunea s-a terminat cu succes după 3 interogări.