==Include(page="template/taskheader" task_id="tvshow")==
 
==Include(page="template/raw")==
 
tvshow
 
Intr-un show de televiziune N concurenti participa intr-o competie 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, S[i], 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 P[i](0<=P[i]<=S[i]). Daca poarta pe care a ales-o el este cea care ascunde premiul atunci punctajul sau va fi S[i]+P[i] iar daca nu a ghicit-o S[i]-P[i]. 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).
 
h2. 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.
 
h2. Date de Intrare
 
Fisierul 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.
 
h2. 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).
 
h2. Restrictii
 
o 1 < N < 301
o Valorile scorurilor sunt numere intregi din intervalul [0, 30000]
o Pentru 40% din teste N <= 17
 
Exemple
 
 
|tvshow.in |tvshow.out |
 
|3 |76 |
|100 25 |1 |
|100 75 |2 |
|100 | |
 
|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. |
 
 
 
 
 
|tvshow.in |tvshow.out |
 
|2 |0 |
|10 3 |0 |
|2 |1 |
 
|Petrica pierde orice suma ar paria. |
 
 
 
 
 
|tvshow.in |tvshow.out |
 
|3 |10 |
|50 31 |1 |
|60 41 |8 |
|10 | |
 
|Pariind 10 puncte Petrica 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. |

==Include(page="template/taskheader" task_id="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, {$S{~i~}$}, 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 {$P{~i~}$} ({$0≤P{~i~}≤S{~i~}$}). Daca poarta pe care a ales-o el este cea care ascunde premiul atunci punctajul sau va fi S{~i~}+P{~i~} iar daca nu a ghicit-o S{~i~}-P{~i~}. 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).
 
h2. 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.
 
h2. 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.
 
h2. 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$}).
 
h2. Restrictii si precizari
 
* $1 < N < 301$
* Valorile scorurilor sunt numere intregi din intervalul $[0, 30000]$
* Pentru {$40%$} din teste $N &le; 17$
 
h2. Exemple
 
table(example). |_. tvshow.in |_. tvshow.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 |
 
h3. 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.
 
==Include(page="template/taskfooter" task_id="tvshow")==

==Include(page="template/taskfooter" task_id="tvshow")==

423