Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | jocul2.in, jocul2.out | Sursă | Tabăra ICHB 2012, Ziua 2, Grupa 2 |
| Autor | Dan Constantin Spatarel | Adăugată de |  Dan-Constantin Spatarel •spatarel |
| Timp execuţie pe test | 0.75 sec | Limită de memorie | 16384 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Jocul2
"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 Vi el calculează ponderea cărţii: Pi = (S xor Vi) + 1. Având toate ponderile calculate, el alege una dintre cărţi cu o probabilitate proporţională cu ponderea sa.
Date de intrare
Fişierul de intrare jocul2.in ...
Date de ieşire
În fişierul de ieşire jocul2.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| jocul2.in | jocul2.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
