ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1036. Lucky Tickets

Another prayer for help
Posted by Toshke 19 Jun 2002 02:27
Reason is of course WA
Here 's my code.
My solution differs much from the other solutions because I count the
matrix kolko with DFS. Thus it is obvius that it's faster but the
memory is going over the limit so I had to use one byte for two
digits. Then I copy the result into the variable result which has 100
bytes and square it. I would be very grateful if someone could see
the error. Thanks, Toshke

type vbroj = array [0..30] of byte;
     vbroj1 = array [0..100] of byte;
var n, s, i, j: longint;
    kolko: array [0..50,0..450] of vbroj;
    mark: array [0..50, 0..450] of boolean;
    result: vbroj1;

function max(a, b: longint): longint;
    begin
        if a > b then max := a else max := b;
    end;

procedure saberi(var a, b: vbroj);
    var pamti: longint;
    begin
        b[0] := max(a[0], b[0])+1;
        pamti := 0;
        for i := 1 to b[0] do begin
            b[i] := a[i] + b[i] + pamti;
            pamti := b[i] div 100;
            b[i] := b[i] mod 100;
        end;
        if b[b[0]] = 0 then dec(b[0]);
    end;

procedure pomnozi(var a, b: vbroj1);
    var c: vbroj1;
        i, j, k: longint;
    begin
        if a[0] = 0 then a[0] := 1;
        if b[0] = 0 then b[0] := 1;
        fillchar(c, sizeof(c), 0);
        for i := 1 to a[0] do
            for j := 1 to b[0] do begin
                k := a[i]*b[j];
                c[i+j-1] := c[i+j-1] + k mod 100;
                c[i+j] := c[i+j] + k div 100;
            end;

        c[0] := a[0] + b[0];
        for i := 1 to c[0]+1 do begin
            c[i+1] := c[i+1] + (c[i] div 100);
            c[i] := c[i] mod 100;
        end;
        while (c[c[0]] = 0) and (c[0] > 1) do dec(c[0]);
        b := c;
    end;

procedure izracunaj(brc, suma: longint);
    var s1, i: longint;
    begin
        if not mark[brc,suma] then begin
            for i := 0 to 9 do begin
                s1 := suma - i;
                if s1 >= 0 then begin
                    izracunaj(brc-1,s1);
                    saberi(kolko[brc-1,s1], kolko[brc,suma]);
                end;
            end;
        end;
        mark[brc,suma] := true;
    end;

procedure ispisi(x: vbroj1);
    var i: longint;
    begin
        if x[0] = 0 then x[0] := 1;
        for i := x[0] downto 1 do begin
            if (x[i] < 10) and (x[0] <> i) then write('0');
             write(x[i]);
        end;
        writeln;
    end;


begin
    read(n, s);
    fillchar(kolko, sizeof(kolko), 0);
    fillchar(mark, sizeof(mark), false);
    kolko[0,0][0] := 1;
    kolko[0,0][1] := 1;
    for i := 0 to 450 do mark[0,i] := true;
    if s mod 2 = 0 then izracunaj(n ,s div 2);
    for i := 0 to 30 do
        result[i] := kolko[n,s div 2][i];
    pomnozi(result, result);
    ispisi(result);
end.