== include(page="template/taskheader" task_id="mole") ==
Poveste şi cerinţă...
Pentru a nu mai întâmpina probleme logistice, comisia lotului de pregătire de anul acesta a decis să stabilească clasamentul celor $N$ participanţi independent de punctajele obţinute la cele două probe de concurs.
h2. Date de intrare
Din fericire pentru tine, însă, există o cârtiţă ({_eng. mole_}), a cărui nume nu îl vom menţiona, care ţi-a divulgat acest secret, astfel că ai aflat intenţiile malefice ale comisiei. Mai mult, persoana este dispusă să te ajute să descoperi clasamentul. Totuşi, pentru a nu fi descoperiţi, aţi hotărât să comunicaţi astfel:
Fişierul de intrare $mole.in$ ...
# Vei întreba cârtiţa un posibil clasament $p{~1~}, p{~2~}, ... , p{~N~}$;
# Cârtiţa va porni de la clasamentul întrebat de tine şi îl va transforma în clasamentul comisiei, interschimbând pe rând locurile a câte doi participanţi. Să presupunem că numărul minim de schimbări este $x$. Cârtiţa îţi va răspunde întrebării cu $x$.
h2. Date de ieşire
h2. Interacţiune
În fişierul de ieşire $mole.out$ ...
h2. Restricţii
* $... ≤ ... ≤ ...$
*Această problema este interactivă.* Vi se pune la dispoziţie funcţia cu următorul cu următorul antet:
== code(cpp)|
int ask(std::vector<int> guess);
==
*Atenţie! Această funcţie nu trebuie implementată de către voi*. Graderul va implementa această funcţie. Argumentul $guess$ reprezintă clasamentul de care veţi întreba. Funcţia va returna numărul minim de interschimbări $x$, descris mai sus. Argumentul $guess$ trebuie să reprezinte o permutare validă a numerelor din intervalul $[1, N]$. În caz contrar, graderul va termina programul din execuţie şi va nota testul ca fiind incorect.
h2. Detalii de implementare
Veţi implementa funcţia cu următorul antet:
== code(cpp) |
std::vector<int> find_standings(int N);
==
Funcţia $find_standings$ va fi apelată o dată. $N$ este numărul de concurenţi.
Funcţia trebuie să returneze, în final, clasamentul căutat. Pentru aceasta, din cadrul ei se poate apela de un număr limitat de ori funcţia de interacţiune $ask$ (vezi secţiunea *Punctare*).
*Din cauza limitărilor impuse de Infoarena şi pentru a reproduce condiţiile din concurs, recomandăm să foloseşti template-urile de 'aici':problema/mole?mole.zip .*
h2. Punctare
table(example). |_. Subtask |_. Punctaj |_. Constrângeri |
| 1
| 7 puncte
| 3 ≤ N ≤ 6
Funcţia ask poate fi apelată de cel mult 1.000 ori.
|
| 2
| 14 puncte
| 3 ≤ N ≤ 100
Funcţia ask poate fi apelată de cel mult 5.000 ori.
|
| 3
| 40 puncte
| 3 ≤ N ≤ 200
Funcţia ask poate fi apelată de cel mult 4.000 ori.
|
| 4
| 16 puncte
| 3 ≤ N ≤ 200
Funcţia ask poate fi apelată de cel mult 2.700 ori.
|
| 5
| 15 puncte
| 3 ≤ N ≤ 200
Funcţia ask poate fi apelată de cel mult 1.800 ori.
|
| 6
| 8 puncte
| 3 ≤ N ≤ 200
Funcţia ask poate fi apelată de cel mult 1.600 ori.
|
h2. Exemplu
table(example). |_. mole.in |_. mole.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
table(example). |_. Intrare |_. Ieşire |
| find_standings(3)
| -
|
| -
| ask({1, 2, 3})
|
| 2
| -
|
| -
| ask({1, 3, 2})
|
| 1
| -
|
| -
| ask({2, 3, 1})
|
| 0
| -
|
| -
| return {2, 3, 1}
|
| OK
| -
|
== include(page="template/taskfooter" task_id="mole") ==
