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.

Download