Fişierul intrare/ieşire:boltz.in, boltz.outSursăRomanian Collegiate Programming Contest 2019
AutorSebastian BuruianaAdăugată deRCPC2019RCPC2019 RCPC2019
Timp execuţie pe test1.0 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Boltz

Inainte de existenta smartphone-urilor, legendele zic ca, pentru a alunga plictiseala, oamenii inventau diferite jocuri pentru a le juca, de exemplu, pe un drum lung cu autocarul.

Un astfel de joc se numeste Boltz. Jucatorii sunt asezati intr-un cerc, si incep sa enumere cu randul numerele naturale. Primul jucator striga 1, urmatorul 2, apoi 3 etc. Pana acum jocul nu este foarte interesant, dar exista o regula in plus. Daca numarul care trebuie rostit contine cifra 7 sau este multiplu de 7, jucatorul trebuie sa strige BOLTZ, dupa care sensul de mers se schimba.

Pentru a intelege mai bine cum functioneaza jocul, mai jos aveti un exemplu cu primele 20 de ture ale unui joc cu 3 jucatori.

Daca un jucator greseste, atunci acesta este eliminat din joc, iar jocul continua de la urmatorul jucator, cu urmatorul numar (nu se schimba sensul, chiar daca numarul ce a fost gresit continea cifra 7). De exemplu, este randul lui Thomas, urmat de Charles, urmat de Ronald. Thomas striga 6, iar Charles ar trebui sa strige BOLTZ. Daca nu o face, el este eliminat din joc, iar Ronald trebuie acum sa strige 8.

Ultimul jucator ramas este castigatorul jocului. Thomas este un admirator al statisticilor, asa ca nu este interesat care dintre jucatori are cele mai mari sanse sa castige, ci care este probabilitatea acestuia sa castige jocul.

Date de intrare

Fişierul de intrare contine pe prima linie N, numarul de jucatori. Urmeaza N linii, fiecare dintre ele descriind unul din jucatori, in ordinea initiala de desfasurare a jocului (prima linie descrie primul jucator).

Fiecare din cele N linii contine doua numere intregi, p si q, separate prin spatiu. p este probabilitatea ca acel jucator sa greseasca atunci cand trebuie sa strige un numar, iar q este probabilitatea de a gresi cand trebuie sa strige BOLTZ.

Probabilitatile sunt exprimate procentual.

Date de ieşire

Pentru jucatorul cu probabilitatea de castig maxima, afisati acea probabilitate, exprimata procentual, cu exact 3 zecimale de precizie.

Restricţii

  • 2 ≤ N ≤ 8
  • 1 ≤ p, q ≤ 99

Exemplu

boltz.inboltz.out
2
50 50
50 50
66.667
boltz.inboltz.out
3
60 65
40 50
20 80
66.331

Explicaţie

Pentru primul exemplu, fiecare jucator are sansa de 50% de a pierde atunci cand vine tura sa. Al doilea jucator are probabilitate mai mare de castig (intuitiv, deoarece primul jucator are mai multe sanse de a gresi); se poate demonstra ca acea probabilitate este egala cu 66.(6)%.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?