Diferente pentru problema/bani intre reviziile #2 si #12

Diferente intre titluri:

bani
Bani

Diferente intre continut:

== include(page="template/taskheader" task_id="bani") ==
Poveste şi cerinţă...
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.
h2. Date de intrare
Fişierul de intrare $bani.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $bani.out$ ...
În fişierul de ieşire $bani.out$ se vor afisa $T$ numere, cate unul pe linie, fiecare reprezentand raspunsul pentru cele $T$ teste.
h2. 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.
h2. Exemplu
table(example). |_. bani.in |_. bani.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
| 1
3 15
10 10 0
10 10 0
5 7 1
| 13.57142857
|
h3. 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.
== include(page="template/taskfooter" task_id="bani") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
9830