Ðîçâ"ÿçîê çàäà÷³ 4 òóðó
program VIO_4;
type
arr=array [0..1000,0..64] of byte;
arrtype=array [0..1000] of word;
var i,j,shug,n,max_sum,q,p:word;
c:array
[1..2,1..1000] of word;
a:^arr;
w,w_2:^arrtype;
f_in,f_out:text;
procedure tabl(ii,sh:word; var a1:byte; var a2:word);
begin
if
w^[ii]>c[2,sh]+w^[ii-c[1,sh]] then
begin
a1:=0;
a2:=w^[ii]
end
else
begin
a1:=1;
a2:=c[2,sh]+w^[ii-c[1,sh]]
end;
end;
begin
new(a);
new(w);
new(w_2);
max_sum:=0;
assign(f_in,'input.txt');
reset(f_in);
readln(f_in,q);
readln(f_in,n);
FillChar(a^,SizeOf(a^),0);
FillChar(w^,SizeOf(w^),0);
FillChar(w_2^,SizeOf(w_2^),0);
for i:=1 to n do
begin
read(f_in,c[1,i]);
readln(f_in,c[2,i]);
end;
close(f_in);
for i:=0 to q do
begin
if
c[1,n]>i then
begin
a^[i,n]:=0;
w^[i]:=0
end
else
begin
a^[i,n]:=1;
w^[i]:=c[2,n]
end;
end;
for shug:=n-1
downto 2 do
begin
for i:=0 to q
do
begin
if
c[1,shug]>i then a^[i,shug]:=0
else
tabl(i,shug,a^[i,shug],w_2^[i]);
end;
for i:=0 to q
do w^[i]:=w_2^[i];
end;
assign(f_out,'output.txt');
rewrite(f_out);
tabl(q,1,a^[q,1],max_sum);
writeln(f_out,max_sum);
p:=q;
for shug:=1 to n
do
begin
if
a^[p,shug]=1 then write(f_out,shug,' ') ;
if
a^[p,shug]=1 then p:=p-c[1,shug]
end;
dispose(a);
dispose(w);
dispose(w_2);
close(f_out);
end.
Òåñò 1 (5 áàë³â)
input.txt
100
5
20 40
40 60
50 100
20 30
10 20
output.txt
190
1 3 4 5
Òåñò 2 (10 áàë³â)
input.txt
100
15
10 212
10 425
10 842
30 102
10 122
15 962
10 181
20 212
16 232
40 856
20 244
12 555
10 269
30 555
15 211
output.txt
3909
2 3 6 10 12 13
Òåñò 3 (20 áàë³â)
input.txt
500
20
100 2112
100 4225
100 6311
101 8412
300 1012
100 1212
100 6412
150 9612
100 1811
200 2112
160 2312
100 8556
100 2494
10 2555
100 3689
100 3177
10 2669
100 2555
150 2411
100 2388
output.txt
38216
4 7 8 12 14 17
Òåñò 4 (30 áàë³â)
input.txt
100
100
40 86
20 25
12 55
10 26
30 55
10 21
10 140
10 84
30 10
10 12
15 96
10 180
20 21
16 23
40 85
20 24
12 55
10 26
30 55
15 21
10 42
10 840
30 10
10 12
15 96
10 310
20 21
16 23
40 85
20 24
15 21
10 42
10 84
30 10
10 12
15 96
10 18
20 21
16 23
40 85
15 21
10 200
10 84
30 10
10 12
15 96
10 18
20 21
16 23
40 85
15 21
10 42
10 84
30 10
10 12
15 96
10 18
20 21
16 23
40 85
15 21
10 42
10 84
30 10
10 12
15 96
10 18
20 21
16 23
40 85
15 21
10 42
10 24
30 10
10 12
15 96
10 18
20 21
16 23
40 85
15 46
10 18
20 21
16 23
40 85
20 24
15 21
10 42
10 24
30 10
10 12
15 96
10 18
20 21
16 23
40 85
20 45
50 19
15 75
20 45
output.txt
2090
7 8 12 22 26 33 42 43 53 63
Òåñò 5 (35 áàë³â)
input.txt
100
130
40 86
20 25
12 55
10 26
40 85
20 24
12 55
10 96
30 55
15 510
10 42
10 84
30 10
10 92
15 96
10 98
20 21
16 23
40 85
20 24
15 21
30 10
10 12
15 96
10 18
20 21
16 23
40 85
15 21
10 42
10 84
30 10
10 12
15 96
10 18
20 21
16 23
40 85
20 24
15 21
10 42
10 84
30 10
10 12
15 96
10 18
20 21
16 23
40 85
15 200
10 42
10 84
30 10
10 12
15 96
10 18
20 520
16 23
40 85
15 21
10 42
10 84
30 10
10 12
15 96
10 18
20 21
16 23
40 85
15 21
10 42
10 84
30 10
10 12
15 96
10 18
20 21
16 23
40 85
15 21
10 42
10 84
30 10
10 12
15 96
10 18
20 21
16 23
40 85
15 96
10 18
20 21
16 23
40 85
20 52
15 21
10 42
10 84
30 10
40 86
20 25
12 55
10 26
40 85
20 24
12 55
10 26
30 55
15 21
10 42
10 84
30 10
10 12
15 96
10 18
20 62
16 23
40 85
20 24
15 21
10 42
12 55
10 26
30 55
15 21
10 42
12 55
10 26
30 55
20 68
output.txt
1684
8 10 12 14 16 31 50 57
