magic

Această problemă este interactivă. Comisia are o valoare pozitivă pe $16$ biți, necunoscută vouă. Această valoare va fi modificată conform următoarei reguli.

1. Voi veți transmite succesiv valori pozitive pe $16$ biți folosind o funcție pusă la dispoziție de către comisie.
2. Comisia va efectua operația sau exclusiv pe biți (cunoscută drept xor) între valoare furnizată de voi și acea valoare necunoscută.
3. Asupra biților valorii obținute comisia va aplica o rotație circulară a biților cu un număr aleator între $0$ și $15$ de poziții (o rotație de $x$ poziții înseamnă mutarea secvenței formate din ultimii $x$ biti de pe ultimele $x$ poziții pe primele $x$ poziții).

Astfel se va obține noua valoare necunoscută în locul vechii valorii.
Aceste reguli se vor aplica de cel mult $100 \ 000$ de ori. Dacă după un număr de aplicări a regulii valoarea necunoscută capătă valoarea $0$ sunteți magici si obțineți puncte (foarte importante în viitor). Dacă nu, nu veți obține nimic.

Programul vostru va trebui să conțină o funcție

void play()

Această funcție trebuie să apeleze de cel mult $100 \ 000$ de ori funcția

int giveValue (int x)

Valoarea parametrului $x$ trebuie să fie egală exact cu valoarea pe care doriți să o transmiteți. Funcția giveValue este pusă la dispoziția voastră de către comisie și va returna $1$ dacă ați ghicit numărul, $0$ altfel.

Restricții și precizări

• Funcția play va fi apelată de maxim $100$ de ori în cadrul unui test
• Nu apelați funcția giveValue de mai mult de $100\ 000$ de ori în implementarea funcției play.
• Numărul furnizat în funcția giveValue trebuie să se afle în intervalul $[0,2^{16})$
• Nu trebuie să implementați funcția main
• Trebuie să includeți fișierul "magic.h"

Exemplu

Grader: play()
Concurent: giveValue(1)
Concurent: giveValue(2)
Concurent: giveValue(16)
Grader: Acordă punctaj!

Explicație

Valoarea secretă este $7=0000000000000111$.

Valoarea devine $7\oplus 1=6=0000000000000110$.
Valoarea devine $3=000000000000011$ după o rotație cu o poziție.

Valoarea devine $3\oplus 2=1=0000000000000001$.
Valoarea devine $16=0000000000010000$ după o rotație cu $12$ poziții.

Valoarea devine $16\oplus 16=0=0000000000000000$.
Valoarea devine $0=0000000000000000$ după o rotație cu $9$ poziții.

Valoarea necunoscută a fost transformată în $0$ după $3$ apeluri!