expected

Expected Velea

== include(page="template/taskheader" task_id="expected") ==

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 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ă) $size[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]$ (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).

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

h2. 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 $size[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$).

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

h2. Date de ieşire

* $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 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.$

* $Pe sistemul pe care se va face evaluarea, pe cât şi pe sistemul concurenţilor, tipul de date long double ocupă 12 octeti (bytes)$

* $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!$*

h2. Exemplu