Fişierul intrare/ieşire:jocul2.in, jocul2.outSursăTabăra ICHB 2012, Ziua 2, Grupa 2
AutorDan Constantin SpatarelAdăugată despatarelDan-Constantin Spatarel spatarel
Timp execuţie pe test0.75 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultateN/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 Vi î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.

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

Date de intrare

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 (Vi).

Date de ieşire

Î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ă.

Restricţii

  • 1 ≤ N ≤ 20
  • 0 ≤ Vi ≤ 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.

Exemplu

jocul2.injocul2.out
1
512
0.05

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?