Cele mai bune solutii pentru problema "Numere"
(ziua2, problema4)

Punctaj Maxim : 50 puncte

Solutii :
Prorocu Angel - Prahova
Comisia Centrala
Fisierele de teste

Program realizat de elevul Prorocu Angel - rezultat final : premiu I - 157 puncte

{$A+,B-,D+,E+,F-,G+,I+,L+,N+,O-,P-,Q-,R-,S+,T-,V+,X+,Y+}
{$M 65384,0,655360}

{pas}

program Numere;

   var a,sol:array[1..10000]of integer;
       x:array[1..100]of integer;
       ci,cs,n:integer;
       f:text;

procedure ReadData;
   var i,j:integer;
   begin
    assign(f,'numere.in');
    reset(f);
    readln(f,n);
    readln(f,ci,cs);
    for i:=1 to n do read(f,x[i]);
    close(f);
   end;

procedure Rezolva;
   var nr,nr1,nr2,i,j,k,l:integer;
   begin
    fillchar(a,sizeof(a),0);
    for i:=n downto 1 do
     begin
      nr:=x[i];
      a[nr]:=1;
      for j:=1 to cs do if a[j]>0 then if j+nr<=cs then
       begin
        if (a[j+nr]=0)or(a[j+nr]>a[j]+1) then a[j+nr]:=a[j]+1;
       end;
     end;
    assign(f,'numere.out');
    rewrite(f);
    nr:=0;
    for i:=ci to cs do
     begin
      nr1:=a[i];
      if x[n]>i then nr2:=0 else if x[n]=i then nr2:=1 else
       if a[i-x[n]]=0 then nr2:=0 else nr2:=1+a[i-x[n]];
      if nr1<>nr2 then
       begin
        inc(nr);
        sol[nr]:=i;
       end;
     end;
    writeln(f,nr);
    for i:=1 to nr do write(f,sol[i],' ');
    close(f);
   end;

begin
 ReadData;
 Rezolva;
end.

[BACK]

Program realizat de Comisia Centrala a Olimpiadei Nationale de Informatica

program numere;
var a,b:array[1..12100] of integer;
    nr:array[1..100] of integer;
    n,incint,sfint:integer;

procedure citire;
 var f:text;
     i:integer;
 begin
  assign(f,'numere.in');
  reset(f);
  readln(f,n);
  readln(f,incint,sfint);
  for i:=1 to n do read(f,nr[i]);
  close(f);
 end;

procedure dinamica1;
 var i,j:integer;
 begin
  for i:=1 to 10000 do a[i]:=-1;
  for i:=1 to n do a[nr[i]]:=1;
  for i:=1 to sfint do
   if a[i]<>-1 then
   for j:=1 to n do
    if (a[i+nr[j]]=-1) or (a[i]+1<a[i+nr[j]]) then a[i+nr[j]]:=a[i]+1;
 end;

procedure dinamica2;
 var i,j:integer;
 begin
  for i:=1 to 10000 do b[i]:=-1;
  b[nr[n]]:=1;
  for i:=1 to sfint do
   if b[i]<>-1 then
   for j:=1 to n do
    if (b[i+nr[j]]=-1) or (b[i]+1<b[i+nr[j]]) then b[i+nr[j]]:=b[i]+1;
 end;

procedure tiparire;
 var f:text;
     i,rez:integer;
 begin
  rez:=0;
  for i:=incint to sfint do
   if a[i]<>b[i] then inc(rez);
  assign(f,'numere.out');
  rewrite(f);
  writeln(f,rez);
  for i:=incint to sfint do
   if a[i]<>b[i] then write(f,i,' ');
  close(f);
 end;

begin
 citire;
 dinamica1;
 dinamica2;
 tiparire;
end.

[BACK]

Fisierele de teste :

Test 1 :
5
10 100
2 3 5 7 9

Test 3 :
20
200 10000
2 14 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 101

Test 4 :
4
8 16
2 4 5 7

Test 5 :
7
13 20
2 4 5 6 7 8 10

Test 6 :
7
45 70
1 13 24 29 39 40 42

Test 7 :
10
30 45
3 4 5 6 7 8 9 10 15 17

Test 8 :
3
10 2000
3 5 8

Test 9 :
4
40 1000
2 10 33 35

Test 10 :
100
310 400
8 11 14 17 20 23 26 29 32 35 38 41 44 47 50 53 56 59 62 65 68 71 74 77 80 83 86 89 92 95 98 101 104 107 110 113 116 119 122 125 128 131 134 137 140 143 146 149 152 155 158 161 164 167 170 173 176 179 182 185 188 191 194 197 200 203 206 209 212 215 218 221 224 227 230 233 236 239 242 245 248 251 254 257 260 263 266 269 272 275 278 281 284 287 290 293 296 299 302 305

[BACK]