== include(page="template/taskheader" task_id="keymess") ==
!>problema/keymess?keymess2.png!
În Tărâmul Ooo, eşti trimis într-o misiune prin Labirintul Biţilor, unde fiecare poartă este încuiată cu o cheie magică. Există exact $N$ chei, fiecare inscripţionată cu un număr de la $0$ la $N$-1. Dar, evident, cineva le-a amestecat complet.
În tărâmul Ooo, esti trimis intr-o misiune prin Labirintul Bitilor, unde fiecare poarta este incuiata cu o cheie magica. Exista exact n chei, fiecare inscriptioanta cu un numar de la 0 la n-1. Dar, evident, cineva le-a amestecat complet.
Singura ta unealtă este o maşinărie ciudată şi pe jumătate stricată, numită Oracolul Bitwise.
Singura ta unealta este o masinarie ciudata si pe jumatate stricata, numita Oracolul Bitwise.
Dacă îi oferi două chei **diferite** $i$ şi $j$, în loc să îţi spună exact ce sunt, maşinăria va spune AND-ul bitwise al numerelor lor:
$query(i, j) = a{~i~} & a{~j~}$
Daca ii oferi doua chei **diferite** i si j, in loc sa iti spuna exact ce sunt, masinaria va spune AND-ul bitwise al numerelor lor:
query(i, j) = a[i] & a[j]
Sarcina ta: reconstruieşte întreaga permutare amestecată de chei $a{~1~}, a{~2~}, … a{~n~}$ folosind numărul minim posibil de întrebări către Oracol.
Sarcina ta: Reconstruieşte intreaga permutare amestecata de chei a{~1~}, a{~2~}, .. a{~n~} folosind numarul minim posibil de intrebari catre Oracol.
h2. Date de intrare
Pe prima linie se află $T$, numărul de teste. Descrierea fiecărui test este următoarea:
h2. Date de intrare
Prima şi singura linie a fiecărui test conţine un întreg $N$.
Pe prima linie se află $T$, numărul de teste. Descrierea fiecarui test este urmatoarea:
h2. Interacţiunea
Prima si singura linie a fiecarui test contine un intreg $N$
Interacţiunea pentru fiecare test începe când numărul $N$ este citit.
Pentru fiecare test:
Pentru a face un query, se afişează o linie în următorul format:
* Pe prima linie se află $N$, $K$.
* $? i j$
h2. Interactiunea
După fiecare astfel de query interactorul vă va răspunde în stdin cu numărul $(a{~i~} & a{~j~})$.
Interactiunea pentru fiecare test incepe cand numarul $N$ este citit.
Pentru a da un răspuns, se afişează o linie în următorul format:
Pentru a face un query, se afiseaza o linie in urmatorul format:
* $! a{~1~} a{~2~} … a{~n~}$
$* ? i j$
Răspunsul nu va fi considerat la numărul de query-uri.
După fiecare astfel de query interactorul vă va răspunde în stdin cu numarul (a[i] & a[j]).
După aceea, continuaţi la următorul test sau terminaţi programul dacă este ultimul test.
Pentru a da un raspuns, se afiseaza o linie in urmatorul format:
Interactorul nu este adaptiv, ceea ce înseamnă că permutarea este predeterminată.
$* ! a{~1~} a{~2~} ... a{~n~}$
După ce printaţi fiecare query, nu uitaţi să afişaţi end of line şi să daţi flush la output. Altfel veţi primi verdictul „Walltime limit exceeded”.
Raspunsul nu este va fi considerat la numarul de query-uri.
Dacă, la orice pas al interacţiunii, citiţi -1 în loc de date valide, soluţia voastră va primi verdictul „Query invalid” din cauza unui query invalid sau a oricărei alte greşeli.
Dupa aceea, continuati la urmatorul test sau terminati programul daca este ultimul test.
h2. Restricţii
Interactorul nu este adaptiv, ceea ce inseamna ca permutarea este predeterminata.
Există două teste cu datele respective:
Dupa ce printati fiecare query, nu uitati sa afisati end of line si sa dati flush la output. Altfel veti primi verdictul de "Walltime limit exceeded".
Primul test:
Daca, la orice pas al interactiunii, cititi -1 in loc de date valide, solutia voastra va primi verdictul de "Query invalid" din cauza unui query invalid sau orice altei greseli.
* $T = 1$
* $N = 2^6^$
h2. Restricţii
Al doilea test:
Există un singur test cu urmatoarele date:
* $T = 20$
* $N = 2^13^$
Funcţia care determină punctajul este următoarea:
Functia care determina punctajul este urmatoarea:
Fie qs = numarul de query-uri
Fie q = numărul de query-uri maxim din unul dintre teste
|_. Numar query-uri |_. Punctaj |
| qs ≤ 16700 | 100 |
| 16700 < qs ≤ 17700 | e^((1000 - (qs - 16700)) / 334) + 80^ |
| 17700 < qs ≤ 90000 | (-71 / 72300) * qs + (23798 / 241) |
| 90000 ≤ qs < 2^26^ | 10 |
| 2^26^ ≤ qs | $0$ |
|_. Număr query-uri |_. Punctaj |
| $10^6^ ≤ q$ | $0$ |
| $90000 ≤ q < 10^6^$ | $10$ | |
| $17700 < q ≤ 90000$ | $(-71 / 72300) * qs + (23798 / 241)$ |
| $16700 < q ≤ 17700$ | $e^((1000 - (qs - 16700)) / 334)^ + 80$ |
| $q ≤ 16700$ | $100$ |
De asemenea, dacă interactorul primeşte mai mult de 10^6^ query-uri in total programul va fi terminat şi veţi primi verdictul "Prea multe queryuri".
Operatorul de conjuncţie biţi & (AND) este un operator binar care are ca rezultat numărul obţinut prin conjuncţia fiecărei perechi de biţi ce apar în reprezentare în memorie a operanzilor:
!problema/keymess?punctare.png!
0 & 0 = 0
0 & 1 = 0
1 & 0 = 0
1 & 1 = 1
Operatorul & (AND) este un operator binar care are ca rezultat numărul obţinut prin conjuncţia fiecărei perechi de biţi ce apar în reprezentarea în memorie a operanzilor:
$0 & 0 = 0$
$0 & 1 = 0$
$1 & 0 = 0$
$1 & 1 = 1$
* Pentru a da flush, puteţi folosi:
* Pentru a da flush, puteti folosi:
fflush(stdout) sau cout.flush() în C++;
sys.stdout.flush() în Python;
verificaţi documentaţia pentru alte limbaje de programare.
fflush(stdout) sau cout.flush() in C++;
sys.stdout.flush() in Python;
verificati documentatia pentru alte limbaje de programare
h2. Exemplu
|_. stdin |_. stdout |_. Explicaţie |
|1| |Se citeşte T|
|4|Se citeşte N| |
|1| |Se citeste T|
|4|Se citeste N| |
| |? 1 2|Query cu i = 1, j = 2|
| $0$| |Se răspunde că (a{~1~} & a{~2~}) = 0|
| |$! 0 1 2 3$|Programul a presupus că a găsit permutarea şi a răspuns|
| $0$| |Se raspunde ca (a{~1~} & a{~2~}) = 0|
| |$! 0 1 2 3$|Programul a presupus ca a gasit permutarea si a raspuns|
== include(page="template/taskfooter" task_id="keymess") ==
== include(page="template/taskfooter" task_id="keymess") ==
