Fişierul intrare/ieşire:bal2.in, bal2.outSursăLot Botosani 2012 - Baraj 3 Seniori
AutorDragos OpricaAdăugată deSpiderManSimoiu Robert SpiderMan
Timp execuţie pe test1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Bal2

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.

Cerinţă

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.

Date de intrare

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 Pi1, Pi2, ..., PiN 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.

Date de ieşire

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.

Restricţii

  • 1 ≤ K ≤ N ≤ 250
  • 0 ≤ Pij ≤ 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.

Exemplu

bal2.inbal2.outExplicaţ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%.
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%.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content