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 alea comisiei nu trebuie sa depaseasca 10-6
Exemplu
| bani.in | bani.out |
|---|---|
| 1 3 15 10 10 0 10 10 0 5 7 1 | This is another text written on multiple lines. |
Explicaţie
...
