661 Reteta

[•DITzoneC]

Aici puteţi discuta despre problema Reteta.

[•toni2007]

sunt cumva testele oficiale de la ONI? k parca pe testu 2 apare o reteta cu medicamentu 13 desi sunt doar 10 medicamente... si nu-mi dau seama dc busesc 3 teste.. desi sursa pare total ok

[•Florian]

Banuiesc ca s-au pastrat testele oficiale.. Testul nr. 1 e asta:

Cod:

10 9
2 3 1 4 6
2 4 2 3 8 9
1 3 5 7 10
1 4 2 4 6 8
1 5 1 3 5 7 9
1 1 10
2 4 2 3 5 9
2 5 4 7 8 10 13
2 6 2 1 3 5 6 7
10 2 5 8 3 10 3 10 10 3

Daca ne uitam cu atentie la a8a reteta, observam ca avem medicamentul 13, care nu exista (fiind doar 10, n=10).
Deci ar fi incalcat enuntul care spune:

Cod:

apoi q numere distincte din multimea { 1, 2, ..., n } reprezentand medicamentele inscrise pe acea reteta;

Deci 13, nu se afla in multimea {1,2, ... ,10}.

In .ok este 36.5. Sursa mea scoate 36.0. Si mie se pare corect, daca nu as lua in seama 13-ele ala. Se obtine cost minim prin alegerea retelor 1,7,8, platind 14,10, respectiv 12 =>total: 36.0

E adevarat ca s-au luat punctaje de 100, dar pe testul asta cum s-ar se obtine 36.5? Si de ce nu e 36.0? De asemenea, ce cauta 13-ele ala acolo? Multumesc anticipat!

                                                                        Florian  

[•gabitzish1]

36.5 se obtine din primele trei retete : {1,4,6} = 14 ; {2,3,8,9} = 13,5 ; {5,7,10} = 9.
 14 + 13.5 + 9 = 36.5.

[•toni2007]

ma rog... acu mia-m dat seama ca erau gresite testele la oni:)) si chiar ma miram atunci cum de luasem doar 70 de puncte dar e ciudat cum unii cu surse gresite au 100... trebea sa se faca o recorectare... + ca sursa lor ia 100 )

si mie imi da tot 36.0 pe testu 1

[•gabitzish1]

Nu cred ca sursele celor care au luat 100 sunt gresite. Sursa mea, de exemplu, numara medicamentele alese si compara suma formata cu maximul doar cand nr_medicamente == n. Pentru testul postat mai sus, nu scoate suma 36.0 pentru ca sunt prea multe medicamente in cazul retelelor 1, 7, 8 (nr_medicamente > n).
Testul e cu siguranta gresit din moment ce e specificat in enunt ca medicamentele inscrise pe reteta sunt de la 1 la n. Nu trebuia sa se intample asta la ONI.

[•toni2007]

si eu fac la fel si verific daca exista toate medicamentele... daca exista atunci verific:

if  (suma<min)
     min=suma;

pe testu unu imi da:

36.0 (costul minim)
1,tip=2 :(1,10) (4,8) (6,10) (1 reprez nr retetei , tipul 2 si valorile din paranteze: prima nr medicamentului si a doua costul acestuia pe fiecare medicament)
7,tip=2 :(2,2) (3,5) (5,3) (9,10)
8,tip=2 :(4,8) (7,3) (8,10) (10,3) (13,0)

[•Florian]

Sursa mea, de exemplu, numara medicamentele alese si compara suma formata cu maximul doar cand nr_medicamente == n.

Eu verific ca toate cele n sa fie alese. Deci, in mod normal nu ar trebui sa fie gresita verificarea mea. Doar ca e din cauza testelor...

[•gabitzish1]

si eu fac la fel si verific daca exista toate medicamentele... daca exista atunci verific:

if  (suma<min)
     min=suma;

pe testu unu imi da:

36.0 (costul minim)
1,tip=2 :(1,10) (4,8) (6,10) (1 reprez nr retetei , tipul 2 si valorile din paranteze: prima nr medicamentului si a doua costul acestuia pe fiecare medicament)
7,tip=2 :(2,2) (3,5) (5,3) (9,10)
8,tip=2 :(4,8) (7,3) (8,10) (10,3) (13,0)

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.

Tu verifici daca ai EXACT cate un medicament ??    retetele 1 si 8 au amandoua medicamentul 4, de aia nu e bun raspunsul tau(facand abstractie de medicamentul 13).

[•toni2007]

da ai dreptate:D 

[•raduzer]

Am schimbat memoria sa fie la fel ca la ONIsi sursele se va face reevaluare. In legatura cu testul gresit am sa ma uit pe el si il voi schimba.

[•INSiDe]

user.cpp:20: error: invalid types 'int [21][float]' for array subscript
user.cpp:55: error: invalid types 'int [20][float]' for array subscript

Primesc eraorea asta la complilare si nu imi dau seama de la ce vine .. imi puteti spun si mie va rog?

[•Florian]

Probabil apelezi o matrice cu a[ x ][ y ], iar y e de tip float.  Uita-te pe linia 20 si linia 55.

[•INSiDe]

m-am uitat pe sursa .. si intradevar era o matrice a [ x ] [ y ] unde y era declarat ca 'float' insa avea valoarea unui nr natural fara zecimale. aceasta problema ne-a fost data la sc si atat am putut sa fac in limita timpului. profesoara nu a stiut sa corecteze problema si mi-a zis sa caut pe net surse de erori posibile la sursa mea..

Cod:

#include <fstream.h>
int main()
{float r[20][30],s,v[200][30];
 int n,m,i,j,p[21],poz,poz2,k,x2,min,max,gasit,aux[20],x3;
 ifstream f("reteta.in");
 ofstream g("reteta.out");
 f>>n; f>>m;
 for (i=1;i<=m;i++)
    {f>>r[i][1]>>r[i][2];
     for(j=3; j<=r[i][2]+2; j++)
       f>>r[i][j]; }
 for (i=1; i<=n; i++)
   f>>p[i];
       //citiri

 for (i=1; i<=m;i++)
  {s=0;
   for(j=3; j<=r[i][2]+3; j++)
    {x2 = r[i] [j];
      s = s + p[x2];}
   if (r [ i ] [1]==1)
    r [ i ] [ 0 ] = s;
   else
    r [ 1 ] [ 0 ] = s / 2;}   // calculam valoarea fiecarei retete

 poz=1;
 for(i=m;i>=1;i--)
  {j=1;
   while (i+j<=m+1)
    {poz2=2;
     v[poz][1]=i;
     for (k=j; k<=i+j-1; k++)
       {v[poz][0]=v[poz][0] + r[k][0];
				v[poz][poz2]=k;
				poz2++;}
     j++;poz++;}}  // aflam valoarea tuturor combinatiilor de retete posibile


 max=1;
 for (i=1;i<=n;i++)
   max=max+p[i];

 gasit=0;
 while (gasit==0)
  { min=max;poz2=0;
    for(i=1;i<=poz-1; i++)
     if (min > v [ i ] [ 0 ] )
      {min = v [ i ] [ 0 ];
       poz2=i;}               //gasim pretul minim din retetele gasite
    for(i=1;i<=n;i++)
       aux[i]=0;
    for(i=2;i<=v[poz][1];i++)
      {x2=v[poz2][i];
       for (j=3; j<=r[x2][2]+3; j++)
	  {x3=r[x2][j];
	   aux[x3]=1;}}
    gasit=1;
    for(i=1;i<=n;i++)        // verificam daca valorile gasite sunt favorabile
     if(aux[i]==0)
       gasit=0;
    if(gasit==1)
      g<<v[poz][0];         // afisare
    else
      v[poz][0]=max;
	 }
 f.close();
 g.close();
 return 0;
 }

V-as fi recunoscator daca mi-ati spune unde este gresala ( pt a functiona algoritmul n pt a lua 100 pct pe problema  ) .mc

Editat de admin: Pentru a include cod trebuie sa folosesti tagul code, nu quote .

[•raduzer]

Testul 1 a fost modificat si s-a reevaluat problema.

[•danal182001]

Buna seara tuturor,
am aflat de problema ivita din neatentie la unul din testele de la problema reteta, clasa a 8-a.
Am verificat testul. Intradevar medicamentul 13 nu are ce cauta pe reteta respectiva. Cum n=10 si deja 4 medicamente erau plasate... in cadrul retetei, mai existau 6 variante posibile. Oricare medicament plasat nu introducea reteta in solutie, deci fisierul de iesire ramane corect.
TOATE sursele au fost reevaluate inlocuindu-se medicamentul 13 cu 9 (ales evident la intamplare din cele 6 variante). NICI unul din punctajele obtinute de concurenti nu s-a modificat.
Inchei acest mesaj cu scuzele de rigoare pentru situatia neplacuta creata si cu asigurarea ca in testele de la problemele propuse de mine nu va mai apare numarul 13...

prof Dana Lica

[•nod_software]

   Nu erea neaparat obilgatoriu sa modificati testul 1(micuta capcana, trap), daca ati implementat-o foarte bine, va dadea bine si testul 1.

   Eu am facut-o lejer cu backtracking. Generez toate submultimile valide(suma sa fie mai mica decat minim, si sa contina o singura data toate medicamentele mai mici decat n(eu am facut un vector caracteristic, [1..20], si verificam pana la n, iar 13 este mai mare decat N, si nici nu treceam la el). Iar la sfarsit verific daca plata curenta este mai minima atunci min = plata curenta. Sper ca ati inteles...

[•laurion]

Hmm.. pic testul 9 cu "Incorect", de ce oare?  
Mentionez ca folosesc o simpla generare a submultimilor(pe biti).

[•ctlin04]

Imi explica si mie cineva de ce la testul de pe prima pagina se iau retetele 1,7,8, doar in cerinta scrie:
cod:
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.
cod.
iar daca luam luam retetele respective, medicamentul 4 se repeta, sau nu am inteles eu conditia, lamuritima cineva, ca tot iau doar 30 puncte cu incorect pe celelalte, desi inca nu am gasit vre-un test la care programul sa-mi dea raspuns gresit, cred ca pentru testul din comentarii raspunsul e totusi 36.5, nu??

LE:S-a rezolvat pina la urma, totusi am inteles corect conditia 

[•DevilShadow]

Ce ciudat... am trimis o sursa si mi-a dat corect la testul 8, am trimis o alta sursa si mi-a dat corect la testul 1