== include(page="template/taskheader" task_id="bal2") ==
Poveste şi cerinţă...
p<>. Deoarece $K.L 2.0$ s-a săturat de probleme de numărare, el s-a hotărât să organizeze un bal. La bal participă $N$ fete şi $N$ băieţi. Imediat cum au auzit de acest bal, fetele au început să îşi facă planuri, astfel că şi-au notat preferinţele lor pentru partenerii de dans, fiecare fată scriind cât de fericită ar fi dacă ar dansa cu un anumit partener. Din nefericire, fetele şi-au pierdut notiţele şi nu mai ştiu care cu ce băiat voiau să meargă la dans. Totuşi, înainte de a le rătăci, fetele le-au transmis notiţele participanţilor la $LOT$. Prin urmare, pentru fiecare băiat, se cunoaşte probabilitatea ca o fată să fie fericită dacă dansează cu el. În plus, oricare băiat care dansează nu vrea să îşi dezamăgească partenera, iar din această cauză nu poate dansa cu mai mult de $K$ fete fără a-şi diminua performanţele.
h2. Cerinţă
p<>. Voi trebuie să determinaţi probabilitatea maximă care se poate obţine astfel încât cele $N$ fete să fie fericite, iar apoi $K.L 2.0$ vă va recompensa cu $100$ de puncte.
h2. Date de intrare
Fişierul de intrare $bal2.in$ ...
p<>. Fişierul de intrare $bal.in$ conţine pe prima linie numerele naturale nenule $N$ şi $K$, separate printr-un spaţiu, reprezentând numărul de fete şi de băieţi, respectiv numărul maxim de partenere cu care poate dansa un băiat. Următoarele $N$ linii conţin câte $N$ valori naturale. Linia $i+1$ conţine, separate prin câte un spaţiu, valorile $P$~$i1$~, $P$~$i2$~, ..., $P$~$iN$~ care semnifică probabilităţile (exprimate în procente) ca băiatul $i$ să le facă fericite pe fiecare din cele $N$ fete dacă dansează cu ele.
h2. Date de ieşire
În fişierul de ieşire $bal2.out$ ...
Fişierul de ieşire $bal.out$ va conţine pe prima linie un singur număr care reprezintă probabilitatea maximă (exprimată în procente) care se poate obţine ca cele $N$ fete să fie fericite.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ K ≤ N ≤ 250$
* $0 ≤$ $P$~$ij$~ $≤ 100$
* Se consideră corectă o soluţie în care probabilitatea maximă diferă cu cel mult $0.01$ faţă de rezultatul corect.
* Pentru $10%$ din teste, $K = N$
* Pentru alte $10%$ din teste $N ≤ 10$
* $K.L 2.0$ este un roboţel mic, nevinovat şi mai ales singur cuc. Din acest motiv el vă recomandă să folosiţi tipul de date $*double*$.
h2. Exemplu
table(example). |_. bal2.in |_. bal2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
table(example). |_. bal2.in |_. bal2.out |_. Explicaţie |
| 2 2
40 60
25 0
| 24.00
| Primul băiat va dansa cu ambele fete, rezultând o probabilitate de 40% înmulţită cu 60%.
Dacă ar fi dansat al doilea băiat cu prima fată, s-ar fi obţinut o probabilitate mai mică, şi anume de 15%.
|
h3. Explicaţie
...
| 3 1
80 25 11
66 42 11
8 11 100
| 33.60
| Soluţia se obţine dacă dansează primul băiat cu prima fată, al doilea băiat cu a doua fată şi al treilea băiat cu a treia fată: 80% înmulţit
cu 42% înmulţit cu 100%.
|
== include(page="template/taskfooter" task_id="bal2") ==
