### 529 - Addition Chains

Posted:

**Fri Jul 26, 2002 4:36 pm**I can't understand why this program gets Accepted

I use a such algorithm:

1. Consider that sequence <a0,a1,..,am> is good if and only if it is the answer for N = am

2. If sequence <a0,a1,..,am,a(m+1)> is good then the sequence <a0,a1,..,am> is also good.

So, I find all good sequences with length 1, then 2, then 3 etc.

The maximum length of good sequences (for N=1..10000) is 18 (Anyone who get Accepted can said so). There are about 2000000 good sequences of length 17.

But, in my program I consider

maximum length = 15

maximum number of good sequences = 50000

and it get Accepted

I want to get Accepted with correct program!

Can anyone help me?

[pascal]Program p529;

Const MaxD = 15;

MaxN = 10000;

MaxComb = 50000;

Type ChainType = Array[0..MaxD]of ShortInt;

Var Inf : Array[1..MaxN]of ChainType;

NewT,OldT : Array[1..MaxComb]of ChainType;

nt,ot : Integer;

N,i,j : Integer;

Procedure Rec(Step,WT : Integer);

Var i,j,k,p : Integer;

begin

for i:=Step downto 1 do

for j:=Step downto i do begin

p:=OldT[WT,i]+OldT[WT,j];

if (p>OldT[WT,Step]) And (p<=MaxN) then

if Step+1<Inf[p,0] then begin

for k:=1 to Step do Inf[p,k]:=OldT[WT,k];

Inf[p,Step+1]:=p;

Inf[p,0]:=Step+1;

end;

end;

end;

Procedure Rec2(Step,WT : Integer);

Var i,j,k,p : Integer;

begin

for i:=Step downto 1 do

for j:=Step downto i do begin

p:=OldT[WT,i]+OldT[WT,j];

if (p>OldT[WT,Step]) And (p<=MaxN) then

if Step+1=Inf[p,0] then begin

if nt=MaxComb then exit;

nt:=nt+1;

for k:=1 to Step do NewT[nt,k]:=OldT[WT,k];

NewT[nt,Step+1]:=p;

end;

end;

end;

begin

Inf[1][0]:=1;

Inf[1][1]:=1;

for i:=2 to MaxN do Inf[i,0]:=100;

ot:=1;

OldT[1]:=Inf[1];

for i:=2 to MaxD do begin

nt:=0;

for j:=1 to ot do Rec(i-1,j);

if i<MaxD then for j:=1 to ot do Rec2(i-1,j) else Break;

for j:=1 to nt do OldT[j]:=NewT[j];

ot:=nt;

end;

While True do begin

Read(N);

if N=0 then Break;

Write('1');

for i:=2 to Inf[N][0] do Write(' ',Inf[N]

I use a such algorithm:

1. Consider that sequence <a0,a1,..,am> is good if and only if it is the answer for N = am

2. If sequence <a0,a1,..,am,a(m+1)> is good then the sequence <a0,a1,..,am> is also good.

So, I find all good sequences with length 1, then 2, then 3 etc.

The maximum length of good sequences (for N=1..10000) is 18 (Anyone who get Accepted can said so). There are about 2000000 good sequences of length 17.

But, in my program I consider

maximum length = 15

maximum number of good sequences = 50000

and it get Accepted

I want to get Accepted with correct program!

Can anyone help me?

[pascal]Program p529;

Const MaxD = 15;

MaxN = 10000;

MaxComb = 50000;

Type ChainType = Array[0..MaxD]of ShortInt;

Var Inf : Array[1..MaxN]of ChainType;

NewT,OldT : Array[1..MaxComb]of ChainType;

nt,ot : Integer;

N,i,j : Integer;

Procedure Rec(Step,WT : Integer);

Var i,j,k,p : Integer;

begin

for i:=Step downto 1 do

for j:=Step downto i do begin

p:=OldT[WT,i]+OldT[WT,j];

if (p>OldT[WT,Step]) And (p<=MaxN) then

if Step+1<Inf[p,0] then begin

for k:=1 to Step do Inf[p,k]:=OldT[WT,k];

Inf[p,Step+1]:=p;

Inf[p,0]:=Step+1;

end;

end;

end;

Procedure Rec2(Step,WT : Integer);

Var i,j,k,p : Integer;

begin

for i:=Step downto 1 do

for j:=Step downto i do begin

p:=OldT[WT,i]+OldT[WT,j];

if (p>OldT[WT,Step]) And (p<=MaxN) then

if Step+1=Inf[p,0] then begin

if nt=MaxComb then exit;

nt:=nt+1;

for k:=1 to Step do NewT[nt,k]:=OldT[WT,k];

NewT[nt,Step+1]:=p;

end;

end;

end;

begin

Inf[1][0]:=1;

Inf[1][1]:=1;

for i:=2 to MaxN do Inf[i,0]:=100;

ot:=1;

OldT[1]:=Inf[1];

for i:=2 to MaxD do begin

nt:=0;

for j:=1 to ot do Rec(i-1,j);

if i<MaxD then for j:=1 to ot do Rec2(i-1,j) else Break;

for j:=1 to nt do OldT[j]:=NewT[j];

ot:=nt;

end;

While True do begin

Read(N);

if N=0 then Break;

Write('1');

for i:=2 to Inf[N][0] do Write(' ',Inf[N]

*);*

Writeln;

end;

end.[/pascal]Writeln;

end;

end.[/pascal]