platou

Se consideră un şir de $1 \ 048 \ 576$ $(2^{20})$ elemente care sunt numere întregi. Se definesc noţiunile:

• platou ca fiind o secvenţă de elemente egale aflate în vector în poziţii consecutive;
• lungimea unui platou ca fiind numărul de elemente care alcătuiesc un platoul.

Se ştie că în şirul considerat, lungimea maximă a unui platou este $8192$ $(2^{13})$ şi că există cel puţin un platou care are această lungime. Amplasarea unui platou este determinată de poziţia cea mai mică şi de poziţia cea mai mare dintre poziţiile elementelor care alcătuiesc platoul.

Cerinţă

Să se scrie un program care determină amplasarea unui platou de lungime $8192$ în şirul considerat. Dumneavoastră nu cunoaşteţi şirul. Determinarea amplasării platoului se face adresând întrebări comisiei. O întrebare constă în a preciza două poziţii din şir, fie acestea $p_1$ şi $p_2$. Comisia vă dă un răspuns care reprezintă lungimea cea mai mare a unui platou din şir aflat între poziţiile $p_1$ şi $p_2$.

Interacţiune

Programul vostru nu va citi sau scrie din/în niciun fişier și nu va implementa funcția main. În schimb, va avea de implementat funcția

std::pair<int, int> solve();

ce va returna o pereche $(p_1, p_2)$ unde $p_1$ şi $p_2$ reprezintă poziţiile ce determină amplasarea unui platou de lungime $8192$ din şir.
Pentru a afla detalii despre șirul considerat puteți apela funcția

int ask(int p1, int p2);

unde $p_1$, $p_2$ reprezintă poziţiile pentru care faceţi interogarea și funcția returnează o valoare care reprezintă lungimea cea mai mare a unui platou aflat între poziţiile $p_1$ şi $p_2$.

Restricții și precizări

• Poziţiile din şir sunt numerotate de la $1$ la $1 \ 048 \ 576$.
• Fișierul platou.h trebuie inclus
• Se garantează că veți primi răspunul la $20$ de întrebări fără a ieși din limita de timp

Punctaj

Programul vostru obţine $0$ puncte la un test dacă:

• utilizează mai mult de $20$ interogări;
• interoghează cu poziţii incorecte: poziţii mai mici decât $1$ sau mai mari decât $1 \ 048 \ 576$ sau prima poziţie e mai mare strict decât a doua poziţie.
• returnează un răspuns greșit

Altfel, programul vostru obţine pentru un punctaj care depinde de numărul de întrebări după cum urmează :

• pentru cel mult $11$ întrebări obţine $100\%$ din punctaj;
• pentru un număr de întrebări cuprins între $12$ şi $15$ obţine $50\%$ din punctaj;
• pentru un număr de întrebări cuprins între $16$ şi $20$ obţine $25\%$ din punctaj.

Exemplu

• Se apelează ask(1, 8192), interoghez lungimea maximă a unui platou întâlnită între poziţiile $1$ şi $8192$
• Funcția returnează $8192$, semnificând că lungimea maximă este $8192$.
• solve returnează $(1, 8192)$, deoarece știm că un platou cu lungime de $8192$ se află între poziţiile $1$ şi $8192$