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]
