605 Economie

[•savim]

Incearca-le pe astea...

Cod:

14
13
2
189
3
18
29
398
192
38
182
8930
31
34008
18203

12
10
20
30
47815
50000
49999
10
19823
7291
47381
2810
1

18
19272
182
18949
281
38540
283
4840
283
4
42721
46738
4839
47329
25329
47832
33823
3
5

Mie imi da (sursa 100) :

Cod:

2
2
3

1
1

3
3
4
5

Sper sa nu fi bushit ceva 

[•petre]

@savim: al treilea nu ar trebui sa fie 3 3 4 5?

[•savim]

Ba da, ai drepatete, o sa modific in topic. Merci si scuze.

[•Mishu91]

Cum ati scos O(N*Vmax) (k in solutie), k io n-am reusit mai putin de O(N^2*Vmax), pt ca trebuiesc luate toate sumele posibile cu numerele respective din cate am inteles 

[•gabitzish1]

Eu am sortat valorile, si pt fiecare moneda am parcurs de la 0 la Vmax pt a afla sumele ce se pot forma cu el, daca gasesc una care nu se formase pana atunci, inseamna ca moneda respectiva trebuie afisata.

[•Mishu91]

Mersi ... am scos suta  . Faceam o parcurgere care nu-si avea rostu si de asta scoteam O(N^2*Vmax)

[•Bogdan_tmm]

ce nu e bine in abordarea asta?

Cod:

for(i=1;i<=n;i++)
 {
  s+=a[i];
  if(!v[i])
   v[i]=2,min++;
  for(i1=a[i]*2;i1<=max+1;i1+=a[i])
   if(!v[i1]) v[i1]=1;
  for(i1=s;i1<=max+1;i1+=s)
   if(!v[i1]) v[i1]=1;
 }
 fprintf(g,"%ld\n",min);
 for(i1=1;i1<=max+1;i1++)
  if(v[i1]==2)
   fprintf(g,"%ld\n",a[i1]);

Asta dupa ce am sortat vectorul.Vad ca am un timp fffoarte scurt ceea ce a cam ciudat ... max e maximul din vector si cred nu are rost sa merg pana la 50000 ci doar pana la cea mai mare valoare + (1sau0)

[•astronomy]

Tu nu calculezi corect toate sumele care se pot forma. De exemplu daca as avea valorile 2, 5 si 7 cred ca folosind abordarea ta nu ai lua in calcul faptul ca suma 12 se poate forma folosind o valoare 5 si una 7. Trebuie sa folosesti un algoritm gen knapsack pentru a calcula corect acele sume care se pot forma.

[•Bogdan_tmm]

da dar 12 va fi ocupat deja deoarece e multiplu de 2 (v[12]==1).Da,crek nu e suficient sa fac doar acea suma dar daca le'as face cum mai intra programu in O(N*VMAX)?

[•crus]

tocmai am facut problema asta in N*Vmax, intra lejer

[•DraStiK]

primesc kbs la 8 teste 
am declarat un vector de 50000 si 2 de 1000, e prea mult?

[•andrei-alpha]

Nu iei kbs de la prea multa memorie alocata cred, daca era asa, luai ori kbs pe toate testele ori mle(memory limit exceeded) pe unele.
Faci alceva dubios poate iesi din vector.

[•DraStiK]

multumesc, mam prins si eu de ciudatenia mea

intrun final am luat 100

[•Flloryn]

Eu nu inteleg ce se intampla la problema asta, sursa mea este compilata in pascal, am dat si exemplele de pe topic toate merg, dar cand o incarc imi apare "Non zero exit-status"   am verificat sa nu-mi iasa din vector, dar mi se pare in regula.    Ajutati-ma va rog!!!!!!        sursa are codul #304725

[•MciprianM]

Non-zero exit status: Programul tau a returnat o valoare diferita de 0. Cel mai probabil ai uitat return 0; sau ceva similar. Poti primi acest mesaj si in loc de mesajul "Killed by signal": verifica si dupa erorile mentionate deasupra.

Mai multe detalii despre evaluator gasesti aici.http://infoarena.ro/documentatie/evaluator

[•Flloryn]

nu inteleg cum poate returna 0, daca nu folosesc nici o functie, iar programul cand il compilez e ok, da rezultatul bun. (lucrez in pascal, iar aici nu am return 0)

[•MciprianM]

Nu prea stiu Pascal, dar incearca sa scrii exit(0);
Ceva de genul:

Cod:

program economie;
begin
...........
exit(0)
end

;
Desi nu cred ca e asta problema. Mai citeste aici: http://infoarena.ro/forum/index.php?topic=364.0  prima pagina .
Incearca sa cresti dimensiunile vectorilor si sa recitesti codul cu atentie; poate iti gasesti greseala.

[•Flloryn]

Ma tot chinui la problema asta, imi spuneti si mie va rog ce nu e bine in abordarea asta: La toate testele iau raspuns gresit

Cod:

   1. program pascal;  
   2. var f,g:text;    t:array[1..50000] of byte; x,p:array[1..1000] of longint;  
   3.                  max,i,k,j,n,aux,c:longint;  
   4.   procedure citire;  
   5.   begin  
   6.   assign(f,'economie.in'); reset(f);  
   7.   assign(g,'economie.out'); rewrite(g);  
   8.   readln(f,n);  
   9.   
  10.   for i:=1 to n do readln(f,x[i]);  
  11.   max:=50000;  
  12.   for i:=1 to max do t[i]:=1;  
  13.   close(f);  
  14.   end;  
  15.   
  16.   procedure sort(s,d:longint);  
  17.   var a,b,aux,ia:longint;  
  18.   begin  
  19.     a:=s; b:=d;  
  20.     repeat  
  21.     while x[a]<x[b] do b:=b-1;  
  22.     aux:=x[a]; x[a]:=x[b]; x[b]:=aux; ia:=1; a:=a+1;  
  23.     if a<b then  
  24.             begin  
  25.             while x[a]<x[b] do a:=a+1;  
  26.             if a<>b then  
  27.              begin  
  28.              aux:=x[a]; x[a]:=x[b]; x[b]:=aux; ia:=0; b:=b-1;  
  29.              end;  
  30.             end;  
  31.     until b<=a;  
  32.     if a-ia>s then sort(s,a-ia);  
  33.     if a-ia+1<d then sort(a-ia+1,d);  
  34.   end;  
  35.   
  36.   procedure sorte;  
  37.   begin  
  38.   k:=0;  
  39.   for j:=1 to n do  
  40.     begin  
  41.     if  t[x[j]]=1 then  
  42.        begin  
  43.        k:=k+1; p[k]:=x[j]; t[x[j]]:=0;  
  44.        end;  
  45.     for i:=1 to max do  
  46.     if t[i]=0 then  
  47.              begin  
  48.              c:=i+x[j];  
  49.              if (c<=max) then t[c]:=0;  
  50.              end;  
  51.      end;  
  52.   end;  
  53.   
  54.   procedure afisare;  
  55.   begin  
  56.   writeln(g,k);  
  57.   for i:=1 to k do writeln(g,p[i]);  
  58.   close(g);  
  59.   end;  
  60.   
  61. begin  
  62. citire;  
  63. sort(1,n);  
  64. sorte;  
  65. afisare;  
  66. end.  

Imi cer scuze pentru cod  dar chiar nu stiu ce sa mai fac sa iau si eu 100. Va rog sa-l stergeti daca e neregulamentara  expunerea lui.   

[•dornescuvlad]

Rog pe e cineva cu o sursa de 100 sa genereze 2-3 exemple, sa incerc si eu sa ma prind ce gresesc.Pe ale mele da bine, si si pe celelalte postate in topic. 
Multumesc.