Fişierul intrare/ieşire:bani.in, bani.outSursăONIS 2014, Runda 4
AutorDragos OpricaAdăugată defmins123FMI No Stress fmins123
Timp execuţie pe test0.5 secLimită de memorie12192 kbytes
Scorul tăuN/ADificultateN/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 greutatea 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, cate unul pe linie, fiecare reprezentand raspunsul pentru cele T teste.

Restricţii

  • T = 10
  • 1 ≤ N ≤ 750
  • 1 ≤ G ≤ 1000
  • 0 ≤ greu[i] ≤ 1000 pentru 1 ≤ i ≤ N
  • 1 ≤ val[i] ≤ 5000 pentru 1 ≤ i ≤ N
  • 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.inbani.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content