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

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

I have a very slow solution... pleaze tell me if it's right, and if i got a good idea of the problem
Послано Costel::icerapper@k.ro 27 фев 2002 23:29
program timus_p1036;
CONST
  MAXDIGIT      =       150;
  NODEDIGIT     =         8;
  MAXVALUE      =  99999999;
  MODULATOR     = 100000000;
TYPE
  BigNumber=array[1..MAXDIGIT div NODEDIGIT]of longint;

PROCEDURE INIT(var b:BigNumber);
begin
  fillchar(b,sizeof(b),0);
end;

PROCEDURE ADDINT(var b:BigNumber;int:longint);
var  i:longint;
begin
  for i:=1 to MAXDIGIT div NODEDIGIT do
  begin
    b[i]:=b[i]+int;
    int:=b[i] div MODULATOR;
    b[i]:=b[i] mod MODULATOR;
    if int=0 then
      exit;
  end;
end;

PROCEDURE ADDBIG(var b:BigNumber;n:BigNumber);
var  i:longint;
     REST:longint;
begin
  REST:=0;
  for i:=1 to MAXDIGIT div NODEDIGIT do
  begin
    b[i]:=b[i]+n[i]+REST;
    REST:=b[i] div MODULATOR;
    b[i]:=b[i] mod MODULATOR;
  end;
end;

PROCEDURE MULINT(var b:BigNumber;int:longint);
var i:longint;
    REST:longint;
begin
  REST:=0;
  for i:=1 to MAXDIGIT div NODEDIGIT do
  begin
    b[i]:=b[i]*int+REST;
    REST:=b[i] div MODULATOR;
    b[i]:=b[i] mod MODULATOR;
  end;
end;

PROCEDURE PRINTBIG(b:BigNumber);
var k,i,l:longint;
    s:string;
begin
  for i:=MAXDIGIT div NODEDIGIT downto 1 do
  if b[i]<>0 then
    break;
  write(b[i]);
  k:=i-1;
  for i:=k downto 1 do
  begin
    Str(b[i]:8,s);
    l:=1;
    while (s[l]=' ')and(l<=8) do
    begin
      s[l]:='0';
      inc(l);
    end;
    write(s);
  end;
end;

function Greater(a1,a2:BigNumber):boolean;
var
  i:longint;
begin
  for i:=MAXDIGIT DIV NODEDIGIT downto 1 do
    if a1[i]>a2[i] then
    begin
      Greater:=true;
      exit;
    end
  else
    if a1[i]<a2[i] then
    begin
      Greater:=false;
      exit;
    end;
  Greater:=false;
end;

const
  maxs=500;
  maxn=50;
type
  ta=array[0..9,0..maxs]of BigNumber;
var
  a1,a2:ta;
  n,s:longint;
  result:BigNumber;

procedure init_data;
var
  i:longint;
begin
  fillchar(a1,sizeof(a1),0);
  fillchar(a2,sizeof(a2),0);
  init(result);
  for i:=0 to 9 do
    ADDINT(a1[i,i],1);
end;

procedure read_data;
begin
  readln(n,s);
end;

procedure seeifexit;
begin
  if (s mod 2)<>0 then
  begin
    writeln(0);
    halt;
  end;
  s:=s div 2;
end;

procedure OneSwitch;
var
  digit,sum,digit2:longint;
begin
  a2:=a1;
  fillchar(a1,sizeof(a1),0);
  for digit:=0 to 9 do
    for sum:=0 to (maxs-digit) do
      for digit2:=0 to 9 do
        ADDBIG(a1[digit,sum+digit],a2[digit2,sum]);
end;

procedure art_solve;
var
  steps:longint;
begin
  for steps:=2 to n do
    OneSwitch;
end;

procedure result_it;
var
  digit:longint;
begin
  for digit:=0 to 9 do
    AddBig(result,a1[digit,s]);
end;

procedure square_it;
var
  r:BigNumber;
  i:BigNumber;
begin
  r:=result;
  Init(i);
  AddInt(i,2);
  while not Greater(i,r) do
  begin
    AddBig(result,r);
    AddInt(i,1);
  end;
end;

procedure write_sol;
begin
  printbig(result);writeln;
end;

begin
  init_data;
  read_data;
  seeifexit;
  art_solve;
  result_it;
  square_it;
  write_sol;
end.