.campion
conectare | înregistrare | căutare
Pagina principală » Probleme » tvshow

ultima problemă
grupă: mică
sursă: OMI 2016
ultimul articol
autor: Prof. Radu Vişinescu
ultimul software
autor: Prof. Emanuela Cerchez
.campion
tvshow


Timp maxim de executie/test:
0.1 secunde
Memorie totala disponibila/stiva:
16 MB/1 MB

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

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 tvshow.in va contine pe prima linie numarul intreg N reprezentand numarul de concurenti din concurs. Fiecare din urmatoarele N1 linii va contine doi intregi separati printr-un spatiu reprezentand scorul si numarul de puncte pariate pentru fiecare din primii N1 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

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

Exemple

tvshow.in

tvshow.out

3
100 25
100 75
100

76
1
2

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
10 3
2

0
0
1

Petrica pierde orice suma ar paria.

tvshow.in

tvshow.out

3
50 31
60 41
10

10
1
8

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.

Silviu Ionut Ganceanu
Universitatea Politehnica Bucuresti
Contact: tzi_ganci at hotmail dot com

propunător: Prof. Emanuela Cerchez
emanuela.cerchez@gmail.com
Probleme recomandate
De la .campion 2004: cifre1, super, apm, bile1, factk, schimb, caini, secvreg, descfib, maraton, masina1, otilia, multiplu, tub, pasune, remi, m01, robot1, na, sir23, paralel, zaruri, bomboane, dotnet, divizor, tren1, joc5, pachete, soldati1, echipe, omizi, suma1, aedaro, concurs1, windows, comb, renju, latime, vectori, ghici, subperm, puncte, mere1, spirala, distanta, piloti
De acelaşi autor: descfib, otilia, algola, bifo, pal, evantai, treegame
Despre sortare: harta, index, sort, concurs, baby, patrate2, repeat, turist, bacan, toys, scor2, chimie2, politics, submat, scoici, ham, jokes, trecere, multiplu, paralel, sirag1, tabara, munte, sport, puncte1, sume1, schi, granita, tren3, sant1, volei1, poze, maroco, dreptc, dist1, tir1, control, mosia, popas, reactivi, siruri1, coach, anag, matrice4, sume2, urgenta, basm, vot, balcon, joc14, cerc, k1, segm, calorii, ordonare, greutati, arctir, macheta, poligon4, centrala, robot4, lcdr, maxviz, sdmin, qtri, arme, flori1, parc1, mijloc, bile6, proiecte, patru, drept2, subsecvente, cursa1, eoliene, vintage, dreapta, riglef, rebus1, rascoala, zimeria, praslea, aperm, unudoi, gropi1, piscina, restaurare, cabana, culori3
Despre generare: taste, pluricex, balbe, magic3, formule, grup, zmeu, nr01, reteta2, playlist, pizza1, caramele, caini, adevar, prime1, hexa, premii1, carti2, bile4, hof, matrx, cubinvers, arctir, guess, minmax, stele, tablou1, adunscad, sumprod, prisme, operatii1, expeval, triburi1, optim, patru, genab, dineu, cumpanit, nkd, relatii, wb
surse trimise | ajutor