> "Cine nu citește, puncte nu primește"
# Cerință

Tocmai ce ai descoperit un joc retro denumit **BOMBS**. Scopul jocului este de a distruge centrul bazei inamicului tău X, care poate fi reprezentată ca un șir de $N$ camere, numerotate de la $0$ la $N - 1$, exact una dintre aceste camere conținând o bombă. Într-un atac, tu poti alege o cameră pe care să o verifici. Dacă bomba e acolo, atunci o vei putea detona (de la distanță, nu vrem să murim pentru a ne bate inamicii) iar baza lui X va fi distrusă. X este paranoic, așa ca el, inainte de fiecare atac al tău, mută bomba într-una dintre camerele adiacente (din camera $i$ la camera $i + 1$ sau $i - 1$, dacă există). Tu va trebui să găsești o strategie astfel încât să găsești bomba din maxim $2 \cdot N - 4$ verificări. Cu toate acestea, suntem în spiritul crăciunului așa că punctăm și soluții care nu ating neapărat această limită (vezi Punctare).

# Protocol de interacțiune

**NU VEȚI IMPLEMENTA FUNCȚIA MAIN**. Trebuie să începeți prin a include header-ul ```bombs.h``` folosind directiva de preprocesor ```#include "bombs.h"```. În continuare, aveți de implementat funcția `solve`, definită astfel:

```cpp
void solve(int n)
```

Funcția aceasta va fi apelată de grader. Pentru a rezolva problema, puteți apela funcția `bool query(int x)`, implementată de către grader, care va returna `true` dacă bomba se află la poziția $x$ și `false` altfel. Dacă primiți răspunsul `true`, ar trebui să încheiați interacțiunea. Încă puteți face apeluri la funcția `query` și veți primi mereu `true` dar grader-ul vă va contoriza și aceste apeluri, deși nu au niciun folos.

**Aveți la atașamente un exemplu de program pe care îl puteți folosi pentru a vă testa implementarea. Pentru a vă fi mai ușor să testați, acolo este implementată funcția main. În schimb, atunci când trimiteți o soluție, aveți mare grijă să trimiteți DOAR funcția `solve` împreună cu orice altceva este necesar (NU FUNCTIA MAIN)**.

## Exemplu de sursă

```cpp
#include "bombs.h"
#include <vector> //puteti include ce vreti voi

void help(int x){} ///puteti declara funcții ajutatoare
int g; 			   ///sau variabile globale 
void solve(int n){
	for(int i = 0; i < 1000; i++)
		query(0);
}

```

# Restricții și precizări
* $3 \leq N \leq 10000$
* Graderul este adaptiv; cu alte cuvinte, poziția inițială a bombei nu este fixată dar se garantează că există o serie de mutări ale bombei care este consistentă cu răspunsurile pe care le-ați primit până acum de la funcția `query`.
* **Atenție!** Limita de timp include și operațiile făcute de grader. Se va considera că funcția `query` are complexitatea $O(N)$. Putem garanta că limita de timp este suficient de mare pentru a face cel puțin $10^5$ query-uri. 
# Punctare
* Punctajul pe un test depinde de dacă găsiți sau nu bomba și câte apeluri la funcția query folosiți, după următoarele cazuri:
	- nu găsiți bomba: $0%$ din punctajul pe test
	- găsiți bomba în mai mult de $2 \cdot N$ query-uri: $20\%$ din punctajul testului respectiv
	- găsiți bomba în cel mult de $2 \cdot N$ query-uri: $40\%$ din punctajul testului respectiv
	- găsiți bomba în cel mult $2 \cdot N - 2$ query-uri: $60\%$ din punctajul pe testul respectiv
	- găsiți bomba în cel mult $2 \cdot N - 4$ query-uri: $100\%$ din punctajul pe testul respectiv

# Teste
* Problema are trei teste, punctate separat: un test cu $N = 4$ care valorează $30$ de puncte  
  și alte două teste cu $N = 9999$ și $N = 10000$ care valorează $35$ de puncte fiecare.
  
# Exemplu de interacțiune

Grader-ul apelează `solve(3)`. Concurentul apelează `query(1)`, și primește `false`. Concurentul raționează (corect) că bomba trebuie să se afle ori în camera $0$, ori în camera $2$, și la următoarea mutare X este forțat să o mute în camera $1$, așa că apelează din nou `query(1)` și primeste `true`, după care iese din funcția `solve`.