Cal-cule

Te-ai încuiat din greșeală pe din afara grajdului și calul, rămas în interior a schimbat parola de acces. Din fericire ai cel mai deștept cal din lume, capabil să facă calcule complexe și ți-ar putea transmite cu ușurință parola, dar, din păcate încă nu l-ai învățat să comunice eficient.

Încuietoarea funcționează în felul următor: pentru a seta o parolă, trebuie să introduci în sistemul încuietorii, din interiorul grajdului, un șir de $N$ elemente. Apoi sistemul calculează frecvența cu care apare fiecare valoare din șir, sortează aceste frecvențe crescător și salvează noul șir astfel obținut. Acest șir reprezintă noua parolă care trebuie folosită pentru a deschide ușa din exterior.

Calul știe șirul pe care l-a introdus în sistem, dar pentru că este supărat că a fost încuiat în grajd, nu vrea să-ți facă viața prea ușoară. Acesta te lasă să îl întrebi de un subșir din șirul inițial. Pentru acel subșir, calul va calcula frecvențele în același mod ca sistemul încuietorii și îți va răspunde bazat pe șirul obținut.

După cum s-a menționat mai sus, încă nu ai apucat să perfecționezi capacitățile de comunicare ale calului, prin urmare singurul mod prin care acesta îți poate transmite informații prin ușa închisă (calul are o mimică grozavă, dacă ai fi putut să-i vezi fața lungă, treaba era mult mai ușoară) este să o lovească cu copita. Mai exact, pentru o întrebare, el poate lovi cu copita în ușă de un număr de ori din mulțimea $\{0, 1, \ldots K-1\}$.

Cerință

Va trebui să implementezi două funcții:

• descuie_grajdul: care primește ca parametri numerele $N$ și $K$ și pune întrebări calului pentru a afla parola. Pentru a face acest lucru, ți se pune la dispoziție funcția intreaba_cal care va face calculele complexe din capul calului.
• dreseaza_cal: care primește șirul de frecvențe obținut pentru o întrebare a ta, numerele $K$ și $N$ și trebuie să returneze un număr din mulțimea $\{0, 1, \ldots K-1\}$

Interacțiune

Funcția std::vector<int> descuie_grajdul(int N, int K) implementată de concurent:

• primește ca parametri numerele $N$ și $K$
• returnează parola (șirul frecvențelor pentru șirul inițial)
• pune întrebări prin intermediul funcției intreaba_cal

Funcția int intreaba_cal(std::vector<int> indici) dată de comisie:

• primește ca parametru șirul de indici care descrie subșirul din șirul inițial pentru care este interogat calul. Indicii din vector trebuie să fie distincți, și cu valorile cuprinse între $0$ și $N - 1$.
• calculează frecvențele subșirului ales, le ordonează crescător și le transmite funcției dreseaza_cal
• returnează răspunsul primit de la funcția dreseaza_cal nealterat (atâta timp cât răspunul este din mulțimea valorilor permise)

Funcția int dreseaza_cal(int N, int K, std::vector<int> frecvente_sortate) implementată de concurent:

• primește șirul de frecvențe obținut pentru o întrebare, numărul $K$ și numărul $N$
• returnează o valoare din mulțimea $\{0, 1, \ldots K-1\}$
• această funcție nu ar trebui să păstreze memorie de la un apel la altul și să nu depindă decât de memorie locală

Atenție! Codul concurenților va fi rulat în așa fel încât să împiedice folosirea memoriei globale pentru funcția dreseaza_cal.

Atenție! Singurele declarații permise în program sunt: directivele #include, #define (doar pentru constante numerice), using și declarații de funcții. Nu se pot declara variabile globale, statice sau să se returneze pointeri.

Atenție! Trebuie să includeți fișierul calcule.h.

Atenție! Fie $T_i$ numărul de indici cu care este apelată funcția intreaba_cal la a $i$-a interogare, iar $T$ egal cu suma $T_1 + T_2 + \cdots$. Toate soluțiile cu $T \geq 6 \ 000 \ 000$ vor fi considerate incorecte.

Restricții

Fie $Q$ numărul maxim de interogări făcute în cadrul unei grupe și $P$ punctajul maxim al acelei grupe. Atunci, punctajul obținut pe această grupa va fi

In tabelul de mai jos se pot vedea grupele, cu tot cu punctajele maxime ale acestora si limitele $Q_{\text{opt}}$.

Exemplu

Explicație

În exemplul de mai sus este exemplificată interacțiunea. Ne imaginăm că codul secret este egal cu $2, 2, 1, 1, 1$. Comisia transmite concurentului că șirul are 5 elemente, și că $K = 2$. Apoi, concurentul poate întreba calul despre mai multe subșiruri - în speță, concurentul în cazul acesta întreabă despre subșirurile cu indicii $0, 1, 2, 3, 4$, apoi $0, 1, 2, 3$, apoi respectiv $1, 2, 3, 4$. În aceste subșiruri, șirul de frecvențe calculat este $2, 3$, apoi $2, 2$, apoi $1, 3$. Funcția dreseaza_cal descrie informația transmisă de cal concurentului - în cazul acesta el transmite 1, apoi 0, apoi 0 din nou. Concurentul apoi își dă seama că șirul total de frecvențe este $2, 3$, pe care îl și returnează.