Infoleague April Fools Contest 2024 | Cel mai tare hack

Bunicu zice așa frate... este o vorbă: "Lupu-și schimbă părul, dar tot mănâncă oi." - Bunicu, "Cel mai tare hack"

Cerință

În urma unui flood de la dușmani, Bunicu și-a pierdut cele două portofele undeva pe axa Ox. Pentru a le găsi, Bunicu își va folosi arma secretă: cel mai tare hack.

Dacă Bunicu se află la coordonata $x$ și cele două portofele se află la coordonatele $a$, respectiv $b$ ($-10^4 \le x,a,b \le 10^4$, $a<b$), atunci cel mai tare hack va calcula suma distanțelor de la Bunicu la cele două portofele (adică $|x-a|+|x-b|$).

Ajutați-l pe Bunicu să își găsească portofelele, folosind cel mai tare hack de cât mai puține ori.

Protocol de interacțiune

Concurentul va trebui să implementeze următoarea funcție:

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

Această funcție va returna o pereche de numere întregi $(a,b)$ ($-10^4 \le a<b \le 10^4$), coordonatele portofelelor pierdute.

Concurentul va putea apela următoarea funcție pentru a vedea suma distanțelor de la Bunicu (care se află la coordonata $x$) la cele două portofele:

int cel_mai_tare_hack(int x);

Pentru orice apel al acestei funcții, $x$ va trebui să respecte $-10^4 \le x \le 10^4$. În caz contrar, sursa trimisă va primi verdictul "Invalid query".

Restricții și precizări

• $-10^4 \le a < b \le 10^4$;
• Trebuie inclus fișierul cel_mai_tare_hack.h în sursele trimise.
• La "Attachments" se poate găsi grader-ul lgrader.cpp, header-ul cel_mai_tare_hack.h și un exemplu de sursă (cel_mai_tare_hack.cpp).

Punctare

Notăm cu:

• optim: numărul de apeluri ale funcției cel_mai_tare_hack de către sursa comisiei
• Q: numărul de apeluri ale funcției cel_mai_tare_hack de către sursa concurentului

Dacă punctajul maxim asociat unui test este $s$, atunci o sursă care identifică corect coordonatele portofelelor va primi pe acel test un punctaj egal cu $s \cdot p$, unde:

• $p=0$, dacă $Q>2 \cdot 10^4+5$
• $p=0.1$, dacă $10^4 < Q \le 2 \cdot 10^4+5$
• $p=0.1 + 0.1 \cdot (4-log_{10}(Q))$, dacă $100 < Q \le 10^4$
• $p=0.3 + 0.1 \cdot \frac{100-Q}{35}$, dacă $65 < Q \le 100$
• $p=0.4 + 0.2 \cdot \frac{65-Q}{30}$, dacă $35 < Q \le 65$
• $p=0.7 - 0.1 \cdot \frac{Q-optim}{35}$, dacă $optim+1 < Q \le 35$
• $p=0.9$, dacă $Q=optim+1$
• $p=1$, dacă $Q \le optim$

Exemplu de interacțiune

• Comisie: citește $a=-3$ și $b=-2$
• Comisie: solve()
• Concurent: cel_mai_tare_hack(-1)
• Comisie: 3
• Concurent: cel_mai_tare_hack(-3)
• Comisie: 1
• Concurent: return {-3,-2}
• Comisie: OK 2 queries used