Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | bani.in, bani.out | Sursă | ONIS 2014, Runda 4 |
| Autor | Dragos Oprica | Adăugată de |  FMI No Stress •fmins123 |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 12192 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Bani
Un tip serios vrea sa faca multi bani. Asa ca el merge in piata cu N obiecte pentru care le stie valoarea, greutatea si daca acestea pot fi partitionate sau nu. Daca un obiect i are valoarea val[i] si greutatea greu[i] si acesta poate fi partitionat, atunci el se poate partitiona in 2 obiecte distincte astfel incat:
- val1[i] + val2[i] = val[i] si greu1[i] + greu2[i] = greu[i] si val1[i] / val[i] = greu1[i] / greu[i]
unde greu1[i] si val1[i] sunt greutatea si valoarea primului din cele doua obiecte obtinute prin partitionare, iar greu2[i] si val2[i] sunt greutatea si valoarea celui de-al doilea. Stiind ca el are un ghiozdan in care poate cara maxim G unitati, voi trebuie sa calculati valoarea maxima pe care o poate castiga tipul.
Date de intrare
Fişierul de intrare bani.in contine pe prima linie un numar T reprezentand numarul de teste. Pentru fiecare test, pe prima linie se afla doua numere N si G reprezentand numarul de obiecte si respectiv grutatea maxima a ghiozdanului. Pe urmatoarele N linii se afla cate 3 numere val[i], greu[i] si part[i] reprezentand valoarea obiectului i, greutatea lui precum si daca acesta poate fi partitionat sau nu.
Date de ieşire
În fişierul de ieşire bani.out se vor afisa T numere, fiecare reprezentand raspunsul pentru cele T teste.
Restricţii
- 1 ≤ N, G ≤ 750
- Daca un obiect i poate fi partitionat atunci part[i] = 1, alftel part[i] = 0.
- Pentru a primi punctajul pentru aceasta problema diferenta in modul dintre solutiile voastre si ale comisiei trebuie sa fie mai mica decat 10-6, iar comisia va sugereaza sa folositi 8 zecimale la afisare.
Exemplu
| bani.in | bani.out |
|---|---|
| 1 3 15 10 10 0 10 10 0 5 7 1 | 13.57142857 |
Explicaţie
Deoarece nu vom putea lua primele 2 obiecte pentru ca sunt prea grele, vom lua unul dintre ele, iar pe al treilea il vom partitiona in doua obiecte astfel incat cu unul din cele doua sa umplem ghiozdanul.
