Triangulation

Anna a desenat un poligon cu $n$ vârfuri numerotate de la $0$ la $n - 1$ în ordinea acelor de ceasornic. Mai târziu a triangulat poligonul desenând $n - 3$ diagonale care nu se intersectează cu excepția posibilă a vârfurilor. O diagonală este o linie dreaptă între două vârfuri diferite care nu au o latură între ele.

Să definim mai întâi distanța de la vârful $A$ la diagonala $D$. Să zicem că începem la vârful $A$ și ne deplasăm la următorul vârf în ordinea acelor de ceasornic până ajungem la unul dintre vârfurile lui $D$. Numărul de muchii traversate îl numim $left\_distance$. Analog, $right\_distance$ este numărul de muchii traversate dacă începem de la $A$ și ne deplasăm în direcția opusă acelor ceasului până ajungem la $D$. Distanța de la $A$ la $D$ este maximul dintre $left\_distance$ și $right\_distance$.

În exemplul din imagine, distanța de la vârful $0$ la diagonala $(1, 5)$ este $2$, cu $left\_distance=1$ și $right\_distance=2$. Pentru diagonala $(0, 5)$ distanța de la vârful $0$ este $5$, cu $left\_distance=5$ și $right\_distance=2$.

Cerință

Anna vrea să facă din acest lucru o provocare pentru Jacob. Jacob nu știe diagonalele desenate. El știe doar valoarea lui $N$, dar o poate întreba pe Anna de mai multe ori despre perechi de vârfuri și ea îi va spune dacă se găsește o muchie între vârfurile acelea. Scopul lui Jacob este să găsească cea mai apropiată (cu noțiunea de distanță de mai sus) diagonală desenată față de vârful $0$. Îl veți ajuta să își îndeplinească scopul întrebând-o pe Anna un număr limitat de întrebări.

Protocol de interacțiune

Trebuie să implementați următoarea funcție în submisia voastră:

int solve (int n);

• Funcția se apelează exact o dată de către evaluator.
• $n$ este numărul de vârfuri ale poligonului.
• Funcția ar trebui să returneze diagonala între niște vârfuri $a$ și $b$ ca un întreg cu valoarea $a \cdot n + b$.
• Dacă sunt mai multe diagonale cu aceeași distanță minimă, puteți să returnați oricare.

Funcția de mai sus poate apela următoarea funcție:

int query (int x, int y);

• $x$ este indicele primului vârf.
• $y$ este indicele celui de-al doilea vârf.
• $0 \leq x, y \leq n - 1$
• Returnează $1$ dacă există o diagonală între $x$ și $y$ și $0$ altfel.

• Pentru a putea apela această funcție, trebuie inclus header-ul triangulation.h în submisia voastră (#include "triangulation.h")!

Restricții și precizări

• $5 \leq n \leq 100$

Punctare

Fie $q$ numărul de interogări ce le faceți pe un singur test. Totodată fie $w = \frac{n \cdot ( n - 3)}{2}$.

• Dacă faceți o interogare invalidă sau ghiciți răspunsul incorect veți primi $0\%$ din puncte pentru un test.
• Dacă $w < q$ veți primi $0\%$ din puncte pentru un test.
• Dacă $n < q \leq w$ veți primi $(10 + 60 \cdot \frac{w - q}{w - n}) \%$ din puncte pentru un test.
• Dacă $q \leq n$ veți primi $100 \%$ din puncte pentru un test.

Exemplu de interacțiune

Urmează un exemplu de input pentru evaluator și apelurile de funcții corespunzătoare. Inputul este cel desenat în imaginea de mai sus.

Testare locală

Aveți la dispoziție fișierul grader_local.cpp în lista de atașamente. Cu ajutorul acestuia puteți să testați sursa local.

Singura linie din input corespunde lui $n$. Evaluatorul va afișa fiecare apel al lui query la stdout și trebuie să îi răspundeți manual cu $1$ sau $0$.