Fişierul intrare/ieşire:expected.in, expected.outSursăLot Focsani 2016, Baraj 3 Seniori
AutorAlexandru VeleaAdăugată dedepevladVlad Dumitru-Popescu depevlad
Timp execuţie pe test0.5 secLimită de memorie128000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Expected Velea

Alex îşi face bagajul şi a ajuns la împachetarea şosetelor. Şosetele lui Alex au doar două dimensiuni, mare şi mică. Şosetele mici le putem considera ca având dimensiunea sizeSmall, iar pe cele mari le putem considera ca având dimensiunea sizeBig. Sertarul lui conţine N şosete în total. Fiecare şosetă are o anumită culoare color(i) şi o anumită dimensiune(mare sau mică) s(i). Alex a decis că, pentru drum, el nu are nevoie decât de K şosete dintre cele N. Aşa ca el alege, pe rând, la întâmplare, câte o şosetă din sertar şi o pune în bagaj. Dacă în sertar mai sunt P şosete cu dimensiunile s(1), s(2), ... s(P), cu fiecare dimensiune egală fie cu sizeSmall fie cu sizeBig, atunci probabilitatea de a alege şoseta i este egală cu s(i) / (s(1) + s(2) + ... + s(P)). Alex ar vrea să fie asortat, aşa că se gândeşte care este probabilitatea ca după ce îşi face bagajul, cel puţin două şosete luate să aibă aceeaşi culoare (chiar dacă ar avea dimensiuni diferite).

Date de intrare

Fişierul de intrare expected.in conţine pe prima linie numărul întreg N, câte şosete sunt în sertar, şi numărul întreg K, câte şosete îşi alege Alex. Pe următoarea linie se vor afla doi întregi sizeSmall şi sizeBig, dimensiunile unei şosete mici, respectiv ale unei şosete mari. Apoi urmează N linii, pe fiecare linie i se va afla perechea formată din color(i) şi s(i), culoarea şosetei i - un număr natural intre 1 şi N - şi dimensiunea şosetei i - fie 0, reprezentând că şoseta este mică şi că are dimensiunea sizeSmall, fie 1 pentru o şosetă mare cu dimensiunea sizeBig.

Date de ieşire

Fişierul de ieşire expected.out va conţine un singur număr real, probabilitatea pe care o caută Alex de a avea cel puţin două şosete de aceeaşi culoare.

Restricţii

  • 1 ≤ N < 200
  • 1 ≤ sizeSmall, sizeBig ≤ 2000
  • Se acorda 100% din punctaj pe test dacă diferenţa absolută dintre răspunsul vostru şi răspunsul corect este cel mult 0.00001 (10-5)
  • Se acorda 40% din punctaj pe test daca diferenta absoluta dintre raspunsul vostru si raspunsul corect este intre 0.01 (10-2) şi 0.00001 (10-5)
  • Se recomandă folosirea tipului de date long double pentru a stoca numerele reale.
  • Pentru funcţiile scanf, printf o variabilă de tip long double se va formata folosind %Lf
  • Atentie! Fisierele de in / out nu au acelasi nume cu problema!

Exemplu

expected.inexpected.out
4 2
1 2
1 1
2 0
1 1
2 1
0.3333333333333
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?