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

I have a very slow solution... pleaze tell me if it's right, and if i got a good idea of the problem
Posted by Costel::icerapper@k.ro 27 Feb 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.