Rezolvare completă PbInfo #1705 Farma

Noile reguli din sistemul sanitar cer ca medicii să nu prescrie pe reţete un anumit medicament, ci să menţioneze substanţa activă. Reţeta este formată din n prescripţii, câte una pentru fiecare substanţă activă prescrisă.

Farmacista de la care cumpăr medicamentele mi-a făcut o listă în care pentru fiecare substanţă activă de pe reţetă sunt trecute medicamentele care conţin substanţa activă respectivă, precum şi preţul pastilelor prescrise din medicamentul respectiv, sub forma următoare:

  • substanţa activă : medicament1 preţ1, medicament2 preţ2, ..., medicamentk preţk

Din păcate, între anumite medicamente există incompatibilităţi şi ca urmare ele nu pot fi administrate simultan, deoarece ar produce reacţii adverse. De aceea, farmacista mea mi-a dat şi o listă de incompatibilităţi, în listă fiind specificate perechi de medicamente incompatibile, sub forma:

  • medicament1/medicament2

Când cumpăr reţeta, eu trebuie să iau câte un medicament pentru fiecare substanţă activă prescrisă de medic şi să am grijă să nu cumpăr medicamente care sunt incompatibile. Desigur, voi cumpăra pastilele prescrise pentru tratamentul complet.

Cerința

Cunoscând lista pe care mi-a dat-o farmacista, precum şi incompatibilităţile dintre medicamente, scrieţi un program care să determine:

  1. câte medicamente am la dispoziţie pentru fiecare substanţă activă;
  2. suma minimă pe care trebuie să o cheltui pentru a cumpăra reţeta.

Date de intrare

Fișierul de intrare farma.in conține pe prima linie numărul natural c, reprezentând cerinţa pe care trebuie să o rezolvăm (1 sau 2). Pe a doua linie se află numărul natural n, reprezentând numărul de substanţe active prescrise de medic. Pe următoarele n linii se află lista pe care mi-a dat-o farmacista, pe fiecare linie fiind specificată o substanţă activă, urmată de medicamentele care conţin această substanţă şi preţurile lor, sub forma precizată în enunţ. Pe următoarea linie se află un număr natural m, reprezentând numărul de perechi de medicamente existente în lista de incompatibilităţi. Pe următoarele m linii sunt scrise perechile de medicamente incompatibile, câte o pereche pe o linie, sub forma precizată în enunţ.

Date de ieșire

Dacă cerinţa este 1, fişierul de ieşire farma.out va conţine n linii, pe linia i (1≤i≤n) fiind scris numărul de medicamente disponibile pentru substanţa activă descrisă pe linia i+1 în fişierul de intrare.

Dacă cerinţa este 2, fişierul de ieşire farma.out va conţine o singură linie pe care va fi scris un număr natural reprezentând suma minimă pe care trebuie să o plătesc pentru a cumpăra reţeta, în condiţiile descrise în enunţ.

Restricții și precizări

  • 0 < n < 10
  • 0 ≤ m ≤ 1400
  • Denumirile substanţelor active şi ale medicamentelor sunt şiruri de maximum 30 de litere mici ale alfabetului englez. Un medicament poate apărea în lista unei singure substanţe active.
  • Preţurile pastilelor sunt numere naturale nenule strict mai mici decât 1000.
  • Pentru fiecare substanţă activă există cel mult 9 medicamente care să conţină substanţa activă respectivă.
  • În fiecare pereche din lista de incompatibilităţi se află medicamente care conţin substanţe active diferite.
  • În lista de medicamente corespunzătoare fiecărei substanţe active pot exista oricâte spaţii, dar lungimea oricărei linii nu depăşeşte 700 de caractere.
  • Pentru datele de test există întotdeauna soluţie.
  • Pentru teste valorând 10% din punctaj cerinţa este 1.

Exemplul 1

farma.in

1
3
metformin:siofor 10,glibomet 30,bidiab 60,gliformin 10
ibuprofen:nurofen 24,advil     35,         ibusinus 9
  diclofenac : diclac 28 ,   voltaren 50, cambia 102
0

farma.out

4
3
3

Explicație

Există 4 medicamente pentru prima substanţă activă, 3 medicamente pentru cea de a doua şi tot 3 medicamente pentru cea de a treia.

Exemplul 2

farma.in

2
3
metformin:siofor 10,glibomet 30,bidiab 60,gliformin 10
ibuprofen:nurofen 24,advil 35,         ibusinus 9
  diclofenac : diclac 28 ,   voltaren 50, cambia 102
5
siofor/diclac
gliformin/diclac
ibusinus/siofor
ibusinus/voltaren
bidiab/diclac

farma.out

67

Explicație

Plătim suma minimă 67 dacă vom cumpăra glibomet (preţ 30), ibusinus (preţ 9), diclac (preţ 28).

Observaţi că oricare două medicamente cumpărate sunt compatibile.

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 Farma:

//Em. Cerchez
#include <fstream>
#include <cstring>
#define LGMAX 1004
#define INF 1000000000

using namespace std;
ifstream fin("farma.in");
ofstream fout("farma.out");
struct med
      {
        char nume[31];
        int pret;
      };
int suma, smin=INF;
int sol[10];
int solmin[10];
med a[10][10];
int n, cerinta;
int lg[10];
char s[LGMAX];
bool d[100][100];

void  citire();
void  sortare();
void  generare();
int verif(int vf);
int nr(char *s);
int cauta(char * s);
int main()
{ int i;
  citire();
  if (cerinta==1)
     for (i=1; i<=n; i++) fout<<lg[i]<<'\n';
     else
     {
      generare();
      fout<<smin<<'\n';
      //for (i=1; i<=n; i++)  fout<<a[i][solmin[i]].nume<<' '<<a[i][solmin[i]].pret<<'\n';
     }
  fout.close();
  return 0;
}

void  citire()
{char c, *p;
 int i, poz1, poz2, m;
 fin>>cerinta>>n; fin.get(c);
 for (i=1; i<=n; i++)
     {
      fin.getline(s,LGMAX);
      p=strtok(s,":");
      do
      {
         p=strtok(NULL,", ");
         if (!p) break;
         strcpy(a[i][++lg[i]].nume,p);
         p=strtok(NULL,", ");
         a[i][lg[i]].pret=nr(p);
      }
      while (1);
     }
 sortare();
 fin>>m; fin.get(c);
 for (i=1; i<=m; i++)
      {fin.getline(s,LGMAX);
       p=strchr(s,'/');
       *p=NULL;
       poz1=cauta(s);
       poz2=cauta(p+1);
       d[poz1][poz2]=d[poz2][poz1]=1;
      }
 }


void  sortare()
//sortez medicamentele de pe fiecare linie crescator dupa pret
{int i, j, sch;
 med aux;
 for (i=1; i<=n; i++)
     {
       do
       {
           sch=0;
           for (j=1; j<lg[i]; j++)
               if (a[i][j].pret>a[i][j+1].pret)
                  {
                    aux=a[i][j]; a[i][j]=a[i][j+1]; a[i][j+1]=aux;
                    sch=1;
                  }
       }
       while (sch);
     }
}
void  generare()
{int vf=1, i;
 sol[1]=0;
 while (vf>0)
       {
         if (vf>n) //solutie completa
            { if (suma<smin)
                 {smin=suma;
                  for (i=1; i<=n; i++) solmin[i]=sol[i];
                 }
              vf--;
            }
            else
            {sol[vf]++; //incrementez pozitia curenta
             if (sol[vf]>lg[vf]) {suma=suma-a[vf][sol[vf]-1].pret; sol[vf--]=0;}
                else
                if (sol[vf]>1)
                   {suma=suma-a[vf][sol[vf]-1].pret+a[vf][sol[vf]].pret;
                    if (suma>=smin)
                       {suma-= a[vf][sol[vf]].pret;  sol[vf--]=0; }
                       else
                       if (verif(vf)) sol[++vf]=0;
                   }
                   else
                   {suma+=a[vf][1].pret;
                    if (suma>=smin)
                      {suma-= a[vf][1].pret;  sol[vf--]=0; }
                      else
                      if (verif(vf)) sol[++vf]=0;
                   }
            }
       }
}

int verif(int vf)
{ int i, pvf=vf*10+sol[vf];
  for (i=1; i<vf; i++)
       if (d[pvf][i*10+sol[i]]) return 0;
  return 1;
}

int nr(char *s)
{int i, rez;
 for (rez=i=0; s[i]; i++)
      rez=rez*10+s[i]-'0';
 return rez;
}

int cauta(char * s)
{int i, j;
  for (i=1; i<=n; i++)
       for (j=1; j<=lg[i]; j++)
           if (!strcmp(s,a[i][j].nume)) return i*10+j;
  return 0;
}

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 #1705 Farma

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1705 Farma 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!