ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1036. Счастливые билеты

Another prayer for help
Послано Toshke 19 июн 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.