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.