== include(page="template/taskheader" task_id="jocul2") ==
Poveste şi cerinţă...
_"Tocmai ai pierdut jocul!"_, spuse bătrânul...
*SPOILER ALERT*
Michael i-a cerut adevăratului domn Jones să părăsească, împreună cu Nikita, Secţiunea Unu. Evident, având planuri mari pentru ea, adevăratul domn Jones l-a refuzat! Michael, convingător prin mijloace neortodoxe, a ajuns la o înţelegere cu tatăl Nikitei.
Michael ştie că bătrânul este un jucător excelent al jocului, aşa că l-a provocat pe acesta la o partidă, înţelegându-se ca învinsul să respecte dorinţa câştigătorului.
*END OF SPOILER*
Regulile oficiale ale jocului sunt următoarele:
* Iniţial, pe masă sunt $N$ cărţi. Fiecare carte are pe ea scris un număr întreg $V{~i~}$ între $0$ şi $1023$.
* Cel care are prima mutare este bătrânul.
* Jucătorul care este la mutare aşteaptă verdictul arbitrului: arbitrul poate decide fie că bătrânul a câştigat, fie că Michael a câştigat, fie că jocul continuă.
* Dacă arbitrul a anunţat că jocul continuă, jucătorul care este la mutare alege o carte şi o ia de pe masă, lăsând rândul celuilalt jucător.
* Dacă pe masă nu a mai rămas nicio carte, arbitrul anunţă imediat că bătrânul a câştigat.
Cunoscând cât de vagi sunt regulile oficiale ale jocului, Michael a studiat toate partidele jucate de bătrân şi a descoperit atât regula nescrisă a jocului, după care arbitrul face anunţurile cât şi strategia de joc a bătrânului.
Arbitrul se uită la cărţile de pe masă şi calculează $S$, suma $xor$ a valorilor acestora. Apoi:
* îl anunţă câştigător pe bătrân cu o probabilitate de $3 / 40 - (S / 1024) / 20$;
* îl anunţă câştigător pe Michael cu o probabilitate de $1 / 40 + (S / 1024) / 20$;
* anunţă continuarea jocului cu o probabilitate de $9 / 10$.
Când trebuie să ia o carte, bătrânul aplică mereu aceeaşi strategie nedeterministă: se uită la cărţile de pe masă şi calculează $S$, suma $xor$ a valorilor acestora. Apoi, pentru fiecare carte $i$, inscripţionată cu valoarea $V{~i~}$ el calculează ponderea cărţii: $P{~i~} = (S xor V{~i~}) + 1$. Având toate ponderile calculate, el alege una dintre cărţi cu o probabilitate proporţională cu ponderea sa.
Jocul nici nu a început încă, doar cărţile au post puse pe masă, însă bătrânul s-a antepronunţat: _"Tocmai ai pierdut jocul!"_. Michael vrea să ştie cât adevăr este în cuvintele bătrânului, aşa că vă întreabă pe voi care îi sunt şansele reale de câştig, dacă va urma o strategie optimă.
h2. Date de intrare
Fişierul de intrare $jocul2.in$ ...
Fişierul de intrare $jocul2.in$ conţine pe prima linie numărul natural $N$, reprezentând numărul de cărţi aflate la începutul jocului pe masă, iar pe a doua linie $N$ numere naturale, reprezentând valorile cărţilor (V{~i~}).
h2. Date de ieşire
În fişierul de ieşire $jocul2.out$ ...
În fişierul de ieşire $jocul2.out$ se va găsi un singur număr real $P$, reprezentând şansele reale de câştig ale lui Michael, dacă va urma o strategie optimă.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 20$
* $0 ≤ V{~i~} ≤ 1023, 1 ≤ i ≤ N$
* Michael este foarte meticulos, aşa că v-a impus să-l calculaţi pe $P$ cu o precizie de 10^-4^.
h2. Exemplu
table(example). |_. jocul2.in |_. jocul2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 1
512
| 0.05
|
h3. Explicaţie
...
Iniţial, bătrânul este la mutare. Arbitrul poate decide cu o probabilitate de $1 / 40 + (512 / 1024) / 20 = 0.05$ victoria lui Michael şi cu o probabilitate de $3 / 40 - (512 / 1024) / 20 = 0.05$ victoria bătrânului. Alternativ, cu o probabilitate de $0.9$ jocul continuă, caz în care bătrânul alege singura carte de pe masă şi este declarat câştigător.
În concluzie, şansele de câştig ale lui Michael sunt de doar $0.05$.
== include(page="template/taskfooter" task_id="jocul2") ==
