Cel mai tare hack

Time limit: 1s Memory limit: 256MB Input: Output:

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 xx și cele două portofele se află la coordonatele aa, respectiv bb (104x,a,b104-10^4 \le x,a,b \le 10^4, a<ba<b), atunci cel mai tare hack va calcula suma distanțelor de la Bunicu la cele două portofele (adică xa+xb|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)(a,b) (104a<b104-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 xx) la cele două portofele:

int cel_mai_tare_hack(int x);

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

Restricții și precizări

  • 104a<b104-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 ss, atunci o sursă care identifică corect coordonatele portofelelor va primi pe acel test un punctaj egal cu sps \cdot p, unde:

  • p=0p=0, dacă Q>2104+5Q>2 \cdot 10^4+5
  • p=0.1p=0.1, dacă 104<Q2104+510^4 < Q \le 2 \cdot 10^4+5
  • p=0.1+0.1(4log10(Q))p=0.1 + 0.1 \cdot (4-log_{10}(Q)), dacă 100<Q104100 < Q \le 10^4
  • p=0.3+0.1100Q35p=0.3 + 0.1 \cdot \frac{100-Q}{35}, dacă 65<Q10065 < Q \le 100
  • p=0.4+0.265Q30p=0.4 + 0.2 \cdot \frac{65-Q}{30}, dacă 35<Q6535 < Q \le 65
  • p=0.70.1Qoptim35p=0.7 - 0.1 \cdot \frac{Q-optim}{35}, dacă optim+1<Q35optim+1 < Q \le 35
  • p=0.9p=0.9, dacă Q=optim+1Q=optim+1
  • p=1p=1, dacă QoptimQ \le optim

Exemplu de interacțiune

  • Comisie: citește a=3a=-3 și b=2b=-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

Log in or sign up to be able to send submissions!