LEM6 - BIRTHDAY
Tác giả: ll931110
Ngôn ngữ: Pascal
Program LEM6;
Const
input = '';
output = '';
Type
arr = array[1..200] of byte;
Var
p: arr;
a: array[1..500] of integer;
F: array[1..500,0..1000] of arr;
d: array[1..500,0..1000] of integer;
n,m,t: integer;
Procedure init;
Var
fi: text;
i: integer;
Begin
Assign(fi, input);
Reset(fi);
Readln(fi, n, m);
For i:= 1 to m do read(fi, a[i]);
Close(fi);
End;
Procedure addbignum(var x,y,z: arr; m,n: integer);
Var
i,k: integer;
Begin
If m > n then k:= m else k:= n;
For i:= 1 to k do
Begin
z[i]:= z[i] + x[i] + y[i];
If z[i] > 99 then
Begin
z[i]:= z[i] - 100;
inc(z[i + 1]);
End;
End;
If z[k + 1] <> 0 then t:= k + 1 else t:= k;
End;
Procedure optimize;
Var
i,k,s: integer;
Begin
Fillchar(F[1], sizeof(F[1]), 0);
Fillchar(p, sizeof(p), 0);
p[1]:= 1;
s:= 0;
F[1,a[1],1]:= 1;
d[1,a[1]]:= 1;
For i:= a[1] + 1 to n do
Begin
addbignum(F[1,i - 1],p,F[1,i],d[1,i - 1],1);
d[1,i]:= t;
End;
For i:= 2 to m do
Begin
s:= s + a[i - 1] + 1;
For k:= s to n do
Begin
addbignum(F[i,k - 1],F[i - 1,k - a[i] - 1],F[i,k],
d[i,k - 1],d[i - 1,k - a[i] - 1]);
d[i,k]:= t;
End;
End;
End;
Procedure printresult;
Var
fo: text;
i: integer;
Begin
Assign(fo, output);
Rewrite(fo);
Write(fo, F[m,n,d[m,n]]);
For i:= d[m,n] - 1 downto 1 do
Begin
if F[m,n,i] < 10 then write(fo, 0);
write(fo, F[m,n,i]);
End;
Close(fo);
End;
Begin
init;
optimize;
printresult;
End.