Te joci un joc cu Joker-ul. El ți-a dat un număr (), și ți-a spus că are ascunse două numere și (). Scopul jocului este să găsești acestea. Ați stabilit că, pentru a îndeplini acest scop, tu poți să îi pui întrebări de următoarea formă:
Îți dau un șir de numere . Spune-mi care este minimul numerelor .
Cu toate acestea, a intervenit o problemă: În limba nativă a Joker-ului, nu există un cuvânt pentru minim, mai degrabă, el a înțeles cuvântul extrem. Astfel, el va răspunde fiecărei întrebări cu maximul sau minimul segmentului din șirul pe care i l-ați dat. Mai mult decât atât, este posibil să îți răspundă cu maximul sau minimul doar ca să te încurce și mai tare.
Joker-ul știe că acest joc este probabil prea greu de câștigat cu forțe proprii. De aceea, el consideră orice pereche de numere un răspuns corect, o pereche care respectă:
, unde s-a notat cu valoarea absolută a numărului .
Cerință
În lumina acestor informații, trebuie să faci tot ce este posibil să găsești un răspuns care să satisfacă criteriul de corectitudine al Joker-ului cu număr minim de întrebări.
Interacțiune
Participanții au la dispoziție următoarele funcții pentru a interacționa cu Joker-ul:
- Funcția următoare primește un șir de numere și returnează fie minimul sau maximul pe segmentul al șirului dat, ales arbitrar de către Joker-ul:
int query(std::vector<int> a);
- Participanții trebuie să apeleze această funcție pentru a furniza răspunsul final, cu perechea presupus corectă, pe care au dedus-o:
void answer(int L, int R);
Participanții trebuie să implementeze doar funcția solve
, care este apelată pentru a rezolva jocul. Nu trebuie să implementeze funcția main
. Codul sursă trebuie să înceapă cu
#include "joker.h"
și să implementeze doar funcția solve(int N);
Important: Tot codul participantului ar trebui să fie scris în solutie.cpp
. Acolo participanții pot defini variabile globale și funcții proprii pentru a facilita rezolvarea problemei.
Fișiere atașate
Participanții au acces la următoarele fișiere:
joker.h
- header-ul care definește funcțiile de interacțiune (query
șianswer
) necesare pentru implementare.sample_submission.cpp
- un exemplu simplu de implementare care execută un query și răspunde cu de fiecare dată.Lgrader.cpp
- un grader de testare pentru participanți, nu cel utilizat oficial, care îi poate ajuta să verifice codul.
Utilizarea Lgrader în Code::Blocks
Pentru a utiliza Lgrader.cpp
în Code::Blocks:
- Creați un proiect nou.
- Adăugați un fișier denumit
solutie.cpp
(selectațiFile > New > Empty File
), unde veți scrie codul soluției. - Adăugați un fișier gol numit
joker.h
și copiați conținutul din fișierul atașatjoker.h
. - Copiați conținutul din
Lgrader.cpp
înmain.cpp
pentru a simula rularea soluției.
După acest setup, scrieți în solutie.cpp
implementarea funcției solve
. Pentru a testa configurația, puteți copia inițial codul din sample_submission.cpp
în solutie.cpp
. Apoi, apăsați F9 sau selectați Build and Run pentru a compila și rula programul.
La rulare, programul va citi valorile , și , și va simula interacțiunea dintre Lgrader
și soluția concurentului, afișând răspunsurile la interogările făcute prin query
și validând răspunsul final oferit prin answer
.
Exemplu de Interacțiune
Considerăm și valorile ascunse , . Segmentul corespunde subșirului din vectorul de intrare. Grader-ul va apela funcția solve(5)
.
Din interiorul funcției solve
, dacă participantul apelează:
int query({5, 3, 8, 1, 6});
Output-ul va fi fie 1
(minimul) sau 8
(maximul) pe segmentul , ales arbitrar de către Joker-ul.
Dacă participantul apelează:
answer(1, 3);
Output-ul va fi:
Correct
Participantul va primi un punctaj calculat conform formulei de evaluare de la secțiunea Grading.
Grading
Fie numărul de query-uri folosite de soluția voastră și numărul minim de query-uri. Fie .
Atenție!, nu puteți face mai mult de de query-uri per test.
Punctajul primit pe un test este