arbore

Cerință

Miruna și Sonia au inventat următorul joc:

• Miruna se gândește la un arbore cu $N$ noduri (numerotate de la $1$ la $N$).
• Sonia îi pune întrebări Mirunei sub forma unui triplet de noduri distincte $(A, B, C)$. Miruna trebuie să calculeze care este nodul $D$ pentru care suma distanțelor la nodurile $A$, $B$ și $C$ este minimă și să i-l spună Soniei.
• Scopul Soniei este să afle structura arborelui folosind un număr cât mai mic de întrebări.

Dându-se un arbore cu $N$ noduri, scrieți un program care îi află toate muchiile folosind un număr cât mai mic de întrebări.

Interacțiune

Programul vostru nu va implementa funcția main și nu se va folosi de niciun fișier text. În schimb, va implementa funcția

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

ce va returna un vector cu $N - 1$ perechi de valori ce reprezintă muchiile arborelui cu $N$ noduri și structura căutată. În cadrul funcției puteți interacționa cu funcția

int query(int A, int B, int C);

implementată de comisie, ce va returna nodul pentru care suma distanțelor la nodurile $A$, $B$ și $C$ este minim.

Restricții și precizări

• Funcția solve va fi apelată de maxim $T \leq 5$ ori în cadrul unui test
• $3 \leq N \leq 1 \ 000$

Punctaj

Fie $X$ numărul de întrebări pe care le folosește programul comisiei:

• Dacă programul vostru pune cel mult $2 \cdot X$ întrebări va primi $100\%$ din punctaj.
• Dacă programul vostru pune cel mult $5 \cdot X$ întrebări va primi $50\%$ din punctaj.

Punctajul pentru un test va fi $0$ dacǎ apare una dintre următoarele situaţii:

• Programul vostru folosește mai mult de $5 \cdot X$ întrebări
• Programul vostru depǎşeşte timpul maxim de execuţie/test;
• Programul vostru nu respectǎ protocolul de interacțiune;
• Programul vostru nu „ghicește” toți cei $T$ arbori.

Exemplu de interacțiune

Comisie: solve(3)
Concurent: query(1, 2, 3)
Comisie: return 3
Concurent: return {{1, 3}, {2,3}}
Comisie: solve(4)
Concurent: query(1, 2, 3)
Comisie: 1
Concurent: query(1, 2, 4)
Comisie: 1
Concurent: query(1, 3, 4)
Comisie: 1
Concurent: return {{1,2},{1,3},{1,4}}