Gigel trebuie să cumpere n medicamente, numerotate de la 1 la n. Doctorul i-a dat m rețete de două tipuri, codificate cu numerele 1, 2 astfel:
1 – reţetă necompensată, adică preţul medicamentelor de pe reţetă se achită integral de către cumpărător;
2 – reţetă compensată 50%, adică prețul medicamentelor înscrise pe rețetă se înjumătățește.
Se ştie că pe reţete nu există un alt medicament decât cele numeroatete de la 1 la n şi o reţetă nu conţine două medicamente identice.
Dacă o reţetă este folosită atunci se vor cumpăra toate medicamentele înscrise pe ea.

Cerința

Scrieţi un program care să determine suma minimă de bani necesară pentru a cumpăra exact câte unul din fiecare dintre cele n medicamente, folosindu-se de reţetele avute la dispoziţie.

Date de intrare

Fișierul de intrare reteta1.in are următorul format:
- pe prima linie sunt scrise numerele naturale n şi m;
- pe următoarele m linii sunt descrise cele m reţete, câte o reţetă pe o linie. Linia care descrie o reţetă conţine tipul reţetei (1 necompensată sau 2 compensată), urmat de un număr natural q reprezentând numărul de medicamente de pe reţetă, apoi de q numere distincte din mulţimea {1, 2, ..., n} reprezentând medicamentele înscrise pe acea reţetă;
- pe ultima linie a fişierului de intrare sunt scrise n numere naturale separate prin câte un spaţiu, reprezentând în ordinea de la 1 la n, preţul medicamentelor.
Toate numerele de pe aceeaşi linie sunt separate prin câte un spaţiu.

Date de ieșire

Fișierul de ieșire reteta1.out va conţine o singură linie pe care va fi scris un număr real cu o singură zecimală, reprezentând suma minimă determinată.

Restricții și precizări

1 ≤ N ≤ 20
1 ≤ M ≤ 15
1 ≤ preţul oricărui medicament ≤ 200
Pentru datele de test există întotdeauna soluţie.

Exemplu

reteta1.in

reteta1.out

45.0

Explicație

Soluţia s-a obţinut prin folosirea primei şi celei de a patra reţete. O altă soluţie, dar de cost mai mare, s-ar fi obţinut dacă se folosea reţeta a patra şi cea de a cincea.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema reteta1:

#include <cstdio>
#include <cstring>
using namespace std;

int R[16][21], T[16], C[21], sol[16];
int n, m;
double Sum=10000.0;

int verif();
double suma();


int main ()
{
int i, nr_med, j, x, k;
double s;
long nrsol;
FILE * fin=fopen("reteta1.in","r");
FILE * fout=fopen("reteta1.out","w");

fscanf (fin, "%d %d" , &n , &m );
for ( i=1 ; i<=m ; i++ )
    {
     fscanf (fin, "%d %d" , T+i , &nr_med  );
     for ( j=1 ; j<=nr_med ; j++ )
     {
      fscanf (fin, "%d" , &x );
      R[i][x]++;
     }
    }


for ( i=1 ; i<=n ; i++ ) {fscanf (fin, "%d" , &C[i] );}
nrsol=(1<<m)-1;
//generez submultimi de retete
sol[m]=1;
for (k=0; k<nrsol; k++)
    {
    if (verif())
       {
        s=suma();
        if (s<Sum) Sum=s;
       }
    i=m;
    while (sol[i]) {sol[i]=0; i--;}
    sol[i]=1;
    }

fprintf(fout,"%.1lf",Sum);
return 0;
}


int verif()
{
int uz[21], i, k;
for (i=1; i<=n; i++) uz[i]=0;
for (k=1; k<=m; k++)
    if (sol[k])
       {
       for (i=1; i<=n; i++)
           uz[i]+=R[k][i];
       }
for (i=1; i<=n; i++)
    if (uz[i]!=1) return 0;
return 1;
}

double suma()
{
double s=0;
int k, i;
for (k=1; k<=m; k++)
    if (sol[k])
       {
       for (i=1; i<=n; i++)
           s+=(R[k][i]*C[i])/(double)T[k];
       }
return s;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2413 reteta1

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2413 reteta1 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2413 reteta1