Fişierul intrare/ieşire:tvshow.in, tvshow.outSursă.campion 2005
AutorSilviu-Ionut GanceanuAdăugată de
Timp execuţie pe test0.025 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

TVShow

Intr-un show de televiziune N concurenti participa intr-o competitie pe viata si pe moarte din care doar unul dintre ei poate iesi castigator. Fiecare concurent a adunat pe parcursul emisiunii un numar de puncte, Si, si acum urmeaza proba finala. Fiecare dintre ei trebuie sa aleaga una dintre cele doua porti din fata lor. Doar una dintre ele ascunde in spatele ei marele premiu. De asemenea fiecare concurent parieza un numar de puncte Pi (0≤Pi≤Si). Daca poarta pe care a ales-o el este cea care ascunde premiul atunci punctajul sau va fi Si+Pi iar daca nu a ghicit-o Si-Pi. Concurentul cu punctajul maxim in urma acestei probe va castiga marele premiu. Daca exista mai multe punctaje maxime nu va castiga nimeni. Ultimul concurent, cine altul decat Petrica, se afla in fata unei decizii foarte dificile: el stie punctajele celorlalti concurenti si ce numar de puncte au pariat fiecare dar nu stie ce porti au ales acestia, in schimb stie ca fiecare concurent - chiar si el - are 50% sanse sa ghiceasca poarta castigatoare si 50% sanse sa nu o ghiceasca. Trebuie sa decida ce numar de puncte va paria pentru ca probabilitatea sa de castig sa fie cat mai mare (chiar daca pentru doua moduri de a paria probabilitatile sunt foarte apropiate, diferenta fiind practic nula, Petrica va alege modul pentru care probabilitatea sa de castig este mai mare).

Cerinta

Calculati numarul de puncte pe care trebuie sa-l parieze Petrica pentru a avea sanse de castig cat mai mari. Daca exista mai multe solutii alegeti-o pe cea mai mica. De asemenea aflati si probabilitea maxima de castig pe care o poate avea Petrica.

Date de intrare

Fisierul de intrare tvshow.in va contine pe prima linie numarul intreg N reprezentand numarul de concurenti din concurs. Fiecare din urmatoarele N - 1 linii va contine doi intregi separati printr-un spatiu reprezentand scorul si numarul de puncte pariate pentru fiecare din primii N - 1 concurenti. Ultima linie contine un singur numar intreg reprezentand scorul lui Petrica.

Date de iesire

Pe prima linie a fisierului tvshow.out se va afla numarul de puncte pariat de Petrica. Pe urmatoarele doua linii se vor afla doua numere intregi A si B care reprezinta probabilitatea maxima de castig a lui Petrica sub forma de fractie ireductibila (probabilitatea este egala cu A/B).

Restrictii si precizari

  • 1 < N < 301
  • Valorile scorurilor sunt numere intregi din intervalul [0, 30000]
  • Pentru 40% din teste N ≤ 17

Exemple

tvshow.intvshow.out
3
100 25
100 75
100
76
1
2
2
10 3
2
0
0
1
3
50 31
60 41
10
10
1
8

Explicatii

Pentru primu exemplu, probabilitatea ca Petrica sa castige este de 50% daca alege sa parieze 76 de puncte, indiferent daca primii doi concurenti au ghicit sau nu poarta castigatoare. Daca Petrica a ghicit poarta castigatoare el castiga concursul (acumuland 176 de puncte) iar daca nu a ghicit-o atunci sigur pierde (acumuland 24 de puncte). Daca va paria mai putin de 76 de puncte probabilitatea de a castiga va fi mai mica, iar daca pariaza mai mult probabilitatea va ramane aceeasi.

Pentru cel de-al doilea Petrica pierde orice suma ar paria.

In cel de-al treilea exemplu, daca Petrica pariaza 10 puncte are 12.5% sanse sa castige (el castiga doar in cazul in care primii doi concurenti nu ghicesc poarta si el o ghiceste; in oricare din celelalte cazuri Petrica va pierde). Daca pariaza mai putin Petrica va avea 0% sanse de castig.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content