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 spend three days to do this problem,at last I solve it.(it's much faster than the others)
Posted by geniushjs 11 Aug 2003 09:00
program pp;
type
ss=array[1..100] of integer;
var
a,b:array[0..1000] of ss;
r,h:ss;
st:array[1..1000] of integer;
la,lb:array[0..1000] of integer;
l,lr,lh,n,i,j,s,k,m:integer;
function max(a,b:integer):integer;
begin
if a>b then max:=a else max:=b;
end;
begin
 readln(n,s); if odd(s) then begin writeln(0); halt; end;
 s:=s div 2;
 if (s div n>=10) then begin writeln(0); halt; end;
 if s*2>n*9 then s:=n*9-s;
 for i:=0 to s do
 begin
 if i<=9
  then a[i,1]:=1;
  la[i]:=1;
 end;
 la[0]:=1;la[1]:=1;
 for i:=2 to n do
   begin
   b:=a; lb:=la;
    for j:=1 to s do
     for m:=0 to j-1 do
      if j-m<=9 then
      begin
      for k:=1 to max(la[j],lb[m]) do
       begin
        a[j,k]:=a[j,k]+b[m,k];
        a[j,k+1]:=a[j,k+1]+a[j,k] div 10;
        a[j,k]:=a[j,k] mod 10;
       end;
      while a[j,la[j]+1]<>0 do la[j]:=la[j]+1;
      end;
   end;
 lr:=la[s];lh:=la[s];
 r:=a[s];h:=a[s];
for j:=lr downto 1 do
 begin
  for k:=lh downto 2 do inc(r[j+k-1],r[j]*h[k]);
  r[j] :=r[j]*h[1];
 end;
l:=0;
for j:=1 to lr+lh do
 begin
  inc(l,r[j]);
  r[j] :=l mod 10;
  l:=l div 10;
 end;
if (r[lr+lh]<>0)
  then inc(lr,lh)
  else inc(lr,lh-1);
for i:=lr downto 1 do write(r[i]);
end.
WHO is best!!! my program run with 0.04s,and 59k!!hahaha!!!
Posted by baddiex 6 Sep 2003 14:37
WHO is the best!!! my program run with 0.04s,and 59k!!hahaha!!!
Posted by baddiex 6 Sep 2003 14:38
Somebody wants some hints ? email me:bendixester@hotmail.com
Posted by baddiex 6 Sep 2003 14:42
>
Re: WHO is the best!!! my program run with 0.04s,and 59k!!hahaha!!!
Posted by sukolsak 6 Apr 2005 01:57
0.015 s
Re: I spend three days to do this problem,at last I solve it.(it's much faster than the others)
Posted by mara 7 Apr 2005 00:35
First. Do not post AC codes!
Second. While your code works for 0.14 sec and 824K, mine is 0.015 sec and 522K. So You not so cool, how think!
0.015 sec and 110K :)
Posted by wwwwww 7 Apr 2005 00:59
Re: I spend three days to do this problem,at last I solve it.(it's much faster than the others)
Posted by Фоминых Федор 19 Jul 2005 17:20
AC
0.015
229 КБ