== include(page="template/taskheader" task_id="jocul2") ==

"Tocmai ai pierdut jocul!", spuse bătrânul...

_"Tocmai ai pierdut jocul!"_, spuse bătrânul...

*SPOILER ALERT*

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 între $0$ şi $1023$.

* 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.

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 $3 / 40 - (512 / 1024) / 20 = 0.05$ victoria lui Michael şi cu o probabilitate de $1 / 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") ==