BOMBS

"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:

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ă

#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.