Ãîëîâíà
Îðãêîì³òåò òà æóð³
Ðåºñòðàö³ÿ
Òàáëèöÿ ó÷àñíèê³â
Òðåíóâàëüíèé òóð
Ðîçâ'ÿçîê òðåíóâàëüíîãî òóðó
Ïåðøèé òóð
Äðóãèé òóð
Ðîçâ'ÿçîê 4 òóðó


Ïðîãðàìíèé êîä ðîçâ'ÿçêó ÷åòâåðòîãî òóðó ç ïåðåëiêîì òåñò³â

Ðîçâ"ÿçîê çàäà÷³ 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