jocul2

Jocul2

== 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 î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.
 
 

h2. Date de intrare