== include(page="template/taskheader" task_id="reteta") ==
Poveste si cerinta...
Gigel trebuie sa cumpere $n$ medicamente, numerotate de la $1$ la $n$. Doctorul i-a dat $m$ retete de doua tipuri, codificate cu numerele $1$, $2$ astfel:
$1$ - reteta necompensata, adica pretul medicamentelor de pe reteta se achita integral de catre cumparator;
$2$ - reteta compensata $50%$, adica pretul medicamentelor inscrise pe reteta se injumatateste.
Se stie ca pe retete nu exista un alt medicament decat cele numerotate de la $1$ la $n$ si o reteta nu contine doua medicamente identice.
Daca o reteta este folosita atuni se vor cumpara toate medicamentele inscrise pe ea.
h2. Cerinta
Scrieti un program care sa determine suma minima de bani necesara pentru a cumpara exact cate unul din fiecare dintre cele $n$ medicamente, folosindu-sede retetele avute la dispozitie.
h2. Date de intrare
Fisierul de intrare $reteta.in$ ...
Fisierul de intrare $reteta.in$ are urmatorul format:
* pe prima linie sunt scrise numerele naturale $n$ si $m$;
* pe urmatoarele $m$ linii sunt descrise cele $m$ retete, cate o reteta pe o linie. Linia care descrie o reteta contine tipul retetei ( $1$ necompensata sau $2$ compensata), urmat de un numar natural $q$ reprezentand numarul de medicamenta de pe reteta, apoi $q$ numere distincte din multimea { $1, 2, ..., n$ } reprezentand medicamentele inscrise pe acea reteta;
* pe ultima linie a fisierului de intrare dunt inscrise $n$ numere naturale separate prin cate un spatiu, reprezentand in ordine de la $1$ la $n$, pretul medicamentelor.
Toate numerele de pe aceeasi linie sunt separate prin cate un spatiu.
h2. Date de iesire
In fisierul de iesire $reteta.out$ ...
Fisierul de iesire $reteta.out$ va contine o singura linie pe care va fi scris un numar real cu o singura zecimala, reprezentand suma minima determinata.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 20$
* $1 ≤ M ≤ 15$
* $1$ ≤ pretul oricarui medicament ≤ $200$
* Pentru datele de test exista intotdeauna solutie.
h2. Exemplu
table(example). |_. reteta.in |_. reteta.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| $4 5$
$2 1 3
$2 2 2 3$
$1 1 1$
$1 3 4 1 2$
$1 1 3$
$8 20 2 16$
| $45.0$
|
h3. Explicatie
...
Solutia s-a obtinut prin folosirea primei si celei de a patra retete.
O alta solutie, dar de cost mai mare, s-ar fi obtinut daca se folosea reteta a patra si cea de a cincea.
== include(page="template/taskfooter" task_id="reteta") ==
