Fişierul intrare/ieşire:reteta.in, reteta.outSursăONI 2008, clasa a 8-a
AutorDana LicaAdăugată deraduzerRadu Zernoveanu raduzer
Timp execuţie pe test0.1 secLimită de memorie4736 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Reteta

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 atunci se vor cumpara toate medicamentele inscrise pe ea.

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-se de retetele avute la dispozitie.

Date de intrare

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.

Date de iesire

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.

Restrictii

  • 1 ≤ N ≤ 20
  • 1 ≤ M ≤ 15
  • 1 ≤ pretul oricarui medicament ≤ 200
  • Pentru datele de test exista intotdeauna solutie.

Exemplu

reteta.inreteta.out
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

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content