Fişierul intrare/ieşire:porcjoc.in, porcjoc.outSursăFMI No Stress 6
AutorVlad CostinAdăugată defmins123FMI No Stress fmins123
Timp execuţie pe test0.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Por Costel și Jocul

Într-o zi, Por Costel se plictisea, stând singur în grădina sa şi mâncând porumb. Aşa ca s-a hotărât sa îl cheme la el pe cel mai bun prieten al său, Por Cătălin. Acesta, nefiind un tip sportiv, i-a cerut lui Por Costel sa găsească un joc care să nu necesite mişcare, el putând în cazul ăsta să stea şi să mănânce în continuare.

Por Costel, cel mai deştept dintre porci, a luat o cutie goală de la FCK şi-a pus în ea N bileţele pe care a scris câte un număr, apoi i-a propus prietenului său următorul joc: „Tu(Por Cătălin), alegi un bileţel din cutie pe care îl scoţi, te uiţi la el si îl introduci la loc, apoi eu (Por Costel) voi face acelaşi lucru. Dacă numerele scrise pe bileţele noastre sunt prime între ele, tu câştigi, altfel voi câştiga eu.”

Por Cătălin, fiind puţin paranoic şi isteţ, a intuit că şansa de a câştiga e mai mică de obicei, aşa că l-a întrebat pe Por Costel care este probabilitatea ca el (Por Cătălin) să câştige. Bileţele fiind rupte cu copita, aveau dimensiuni diferite, deci şi probabilităţi diferite de a fi alese. Acum Por Costel vă zice vouă: „Por Cătălin nu ştie să calculeze, eu sunt în grădină. Calculaţi voi!”.

Cerinţă

Cunoscându-se numărul N de bileţele, precum şi perechile de valori (Vi, Pi) (valoare şi dimensiune) pentru fiecare bileţel, calculaţi probabilitatea ca Por Cătălin să câştige (sub forma unei fracţii ireductibile).

Date de intrare

Fişierul de intrare porcjoc.in va conţine pe prima linie numărul natural nenul N iar pe următoarele N linii, perechi de numere naturale nenule (Vi, Pi) reprezentând numărul scris pe al i-lea bileţel şi dimensiunea lui (astfel probabilitatea ca al i-lea bileţel să fie ales va fi egal cu P/S, unde S este suma dimensiunilor celor N bileţele).

Date de ieşire

Fişierul de ieşire porcjoc.out va avea formatul „A/B” , unde A şi B sunt numere naturale prime intre ele.

Restricţii

  • 1 ≤ N ≤ 100.000
  • 1 ≤ Vi ≤ 500.000
  • 1 ≤ Pi ≤ 10.000
  • Pentru 30% din teste , N ≤ 5000

Exemplu

porcjoc.inporcjoc.out
3
1 25
4 25
8 25
5/9

Explicaţie

Posibilităţile de alegere a bileţelelor sunt următoarele: (1,1), (1,4), (1,8), (4,1), (4,4), (4,8), (8,1), (8,4), (8,8). Toate au probabilitate egala, si anume  \frac{25}{75} * \frac{25}{75} (cele scrise ingroşat sunt jocurile în care Por Cătălin câştiga).

Deci probabilitatea sa de a câştiga este: 5/9

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?