I test my program a lot of times and the program pass all the test, but it still fails on Test#7, could somebody provide me with some additional test to check?

It will be great if the result of the test will be large number.

Write me for getting source code valery@uni.lg.ua

I use long numeric and dynamic programme, is there any special case I can't imagine?

My idea is to solve it using DP of course. I have to use large
numbers for the result, unfortunately. Which means, that if I have an
array
50*500*sizeof(large num)
i'll have
25000*sizeof(large num)
large nums have about 100 digits, which is 100 bytes, so
25000*100=2500000=2 500 000 bytes, which is more than 1000K :(
If I use just recursion and do not store the results, I'll get time
limit exceeded.
My idea was to have the large numbers as
struct(=class=record) large {
 char* num;
 int size;
}
and allocate memory enough for each of the digits of every number.
The problem is that in C i have to use mallloc and realloc(I know I
can use new instead of malloc, but realloc is the real problem).
Realloc, however, doesn't work OK on my computer and on TIMUS, as I
have seen it :)) The strange fact is that if I trace the program, it
works fine, and if I run it -> it fails. I have the same problem on
another problem on timus, I do not remember which it was. Maybe
because I am allocating too much memory on too many pieces, which are
very small(a byte per time, about a million of times).

So, I help someone has read that,and that someone is going to help
about
1) What to use to solve the problem?
2) How can I solve the problem with realloc

This is my program:
var
  t,total,k:longint;
  n,s:integer;

procedure init;
begin
  read(n,s);
  total:=0;
  k:=0;
end;

procedure work;
var
  i:integer;
begin
  for i:=9 downto 0 do
    if (total+i<=s div 2)and(k<=n) then
      begin
        inc(k);
        total:=total+i;
        if (total=s div 2)and(k=n) then inc(t)
          else work;
        total:=total-i;
        dec(k);
      end;
end;

procedure print;
begin
  writeln(t*t);
end;

begin
  init;
  work;
  print;
end.

Is there any ways to avoid arithmetics between very long numbers?

Hi
  all i didnt see was s might be 0 !!!!
u should remeber too:
  if odd(s) then writeln(0)
and also some tests:
5 10
---> 15876

50 896
---> 1625625

10 10
---> 4008004

49 2
---> 2401

1 20
---> 0

50 0
---> 1 (which i didnt think!)

Have Nice Time
mail me 4 more help
aidin_n7@hotmail.com

program luckytickets;
var
  cur,nxt: array[0..1000,1..101] of byte;
  i,j,k,n,m,p: longint;
  res,buf : array[1..101] of byte;
procedure printing;
var i: integer;
fl: boolean;
begin
  fl := false;
  for i := 100 downto 1 do begin
    if res[i] <> 0 then fl := true;
    if fl then write(res[i]);
  end;
  if not fl then write('0');
  writeln;
end;
procedure summa(m,n: integer);
var i: integer;
begin
  fillchar(nxt[m],sizeof(nxt[m]),0);
  for i := 1 to 50 do begin
    nxt[m][i+1] := (nxt[m][i]+buf[i]+cur[n][i]) div 10;
    nxt[m][i] := (nxt[m][i]+buf[i]+cur[n][i]) mod 10;
  end;
end;
procedure Kvadrat(k : integer);
var i,j: integer;
begin
  for i := 1 to 50 do begin
    fillchar(buf,sizeof(buf),0);
    for j := 1 to 50 do begin
      buf[i+j] := buf[i+j] + cur[k][i]*cur[k][j] div 10;
      buf[i+j-1] := buf[i+j-1] + cur[k][i]*cur[k][j] mod 10;
    end;
    for j := 1 to 99 do begin
      res[j+1] :=res[j+1] + (res[j] + buf[j]) div 10;
      res[j] := (res[j] + buf[j]) mod 10;
    end;
  end;
end;
begin
  readln(n,k);
  if k mod 2 <> 0 then begin
    writeln('0');
    halt;
  end;
  k := k div 2;
  for i := 0 to 9 do begin
    cur[i][1] := 1;
  end;
  for i := 1 to n-1 do begin
    fillchar(nxt,sizeof(nxt),0);
    for p := 0 to 460 do begin
      for j := 0 to 9 do begin
        buf := nxt[p+j];
        summa(p+j,p);
      end;
    end;
    cur := nxt;
  end;
  Kvadrat(k);
  printing;
end.

type
 long = record
              a:array[1..250]of byte;
              l:byte;
        end;
 arr = array[0..530]of long;
 parr = ^arr;

var a:array[1..2]of parr;
    N,M:integer;
procedure add(var a,b:long);
var l,c,k,i:byte;
begin
  k:=0;
  if a.l>b.l then l:=a.l else l:=b.l;
  for i:=1 to l do
  begin
    c:=a.a[i];
    a.a[i]:=(c+b.a[i]+k)mod 10;
    k:=(c+b.a[i]+k)div 10;
  end;
  a.l:=i;
  if k<>0 then
  begin
    inc(a.l);
    a.a[a.l]:=K;
  end;
end;

procedure mul_i(var a:long;b:longint);
var k:longint;c,i:byte;
begin
  k:=0;
  for i:=1 to a.l do
  begin
    c:=a.a[i];
    a.a[i]:=(c*b+k)mod 10;
    k:=(c*b+k)div 10;
  end;
  a.l:=i;
  while k<>0 do
  begin
    inc(a.l);
    a.a[a.l]:=K mod 10;
    k:=k div 10;
  end;
end;

procedure mul(var a:long);
var tmp,_a:long;
    i,j:byte;
begin
  fillchar(tmp,sizeof(tmp),0);
  for i:=1 to a.l do
  begin
    _a:=a;
    mul_i(_a,a.a[i]);
    for j:=_a.l downto 1 do _a.a[j+i-1]:=_a.a[j];
    for j:=1 to i-1 do _a.a[j]:=0;
    _a.l:=_a.l+i-1;
    add(tmp,_a);
  end;
  a:=tmp;
end;
var i,j,k:integer;
    tmp:parr;
begin
{  assign(input,'1036.dat');reset(input);}
  readln(N,M);
  if M mod 2 = 1 then
  begin
    writeln(0);
    halt;
  end else M:=M div 2;
  new(a[1]);new(a[2]);
  fillchar(a[1]^,sizeof(a[1]^),0);
  fillchar(a[2]^,sizeof(a[2]^),0);
  for i:=0 to 9 do begin a[1]^[i].a[1]:=1;a[1]^[i].l:=1;end;
  for i:=2 to N do
  begin
    for j:=0 to M do
    begin
      for k:=0 to 9 do if j-k>=0 then
      begin
        add(a[2]^[j],a[1]^[j-k]);
      end else break;
    end;
    tmp:=a[1];a[1]:=a[2];a[2]:=tmp;
    fillchar(a[2]^,sizeof(a[2]^),0);
  end;
  mul(a[1]^[M]);
  for i:=a[1]^[M].l downto 1 do write(a[1]^[M].a[i]);
  if a[1]^[M].l = 0 then write(0);
  writeln;
  dispose(a[1]);dispose(a[2]);
end.

dear sir please help me out in the prob
sir i am not understanding the prob
what is mean by"ever ticket  has its 2N-digit number".
and what will be the first digit and what will be the last digit
and what is mean by "the sum of all digits in the number"
when we give 2 2
the answer is 4
how will u please explain me please

const nmax=100;
type mas=array[1..nmax]of longint;
var aa:array[0..500]of mas;
    i:longint;
    s:longint;
    n:longint;
    m,j:longint;
    a,b,c:mas;
function dlina(a:mas):longint;
var i:longint;
begin
 i:=nmax;
 while a[i]=0 do dec(i);
 dlina:=i;
end;
procedure slog(a,b:mas;var c:mas);
var i,d1,d2,max:longint;
begin
 fillchar(c,sizeof(c),0);
 d1:=dlina(a);d2:=dlina(b);
 if d1>d2 then max:=d1 else max:=d2;
 for i:=1 to max do
  begin
   c[i]:=c[i]+a[i]+b[i];
   if c[i]>9 then
    begin
     c[i+1]:=c[i] div 10;
     c[i]:=c[i] mod 10;
    end;
  end;
end;
procedure umn(a:mas;var c:mas);
var i,j,p,z,d:longint;
begin
 d:=dlina(a);
 fillchar(c,sizeof(c),0);
 for i:=1 to d do
  begin
   p:=0;
   for j:=1 to d do
    begin
     z:=a[i]*a[j]+p+c[i+j-1];
     c[i+j-1]:=z mod 10;
     p:=z div 10;
    end;
   c[i+j]:=p;
  end;
end;
begin
 readln(n,s);
 if (s div 2>n*9)or(odd(n)) then
  begin
   writeln(0);
   halt;
  end;
 if n=1 then
  begin
   if s>9 then
    writeln(0)else writeln(1);
    halt;
  end;
 s:=s div 2;
 aa[0][1]:=1;
 for i:=1 to n do
  begin
  if s>9*i then m:=0 else m:=s;
   for j:=1 to m do
    begin
    slog(aa[j-1],aa[j],c);
    aa[j]:=c;
    end;
  end;
 umn(aa[m],c);
 for i:=dlina(c)downto 1 do
  write(c[i]);
 writeln;
end.

{$N+,s-}
Program Lucky_ticket;

Type xm=array[-50..200] of integer;
     Lion=array[0..1,-50..1000] of ^xm;

Var k,i,j,m,n,u,v,t,t1:Longint;
    q:double;
    a:Lion;
    LL:array[0..1,-100..1000] of integer;
    c:array[-100..1000] of longint;

Procedure Go(x,y:longint);
var i,j,k,L:longint;
begin
  if LL[t,x]>LL[t1,y] then L:=LL[t,x]
  else L:=LL[t1,y];
  for i:=1 to L do
  begin
    inc(a[t,x]^[i],a[t1,y]^[i]);
    if a[t,x]^[i]>9 then
    begin
      dec(a[t,x]^[i],10);
      inc(a[t,x]^[i+1]);
    end;
  end;
  if a[t,x]^[L+1]<>0 then LL[t,x]:=L+1
  else LL[t,x]:=L;
end;

Procedure Cheng(x:integer);
var i,L:longint;
begin
  fillchar(c,sizeof(c),0);
  for i:=1 to LL[t,x] do
  for j:=1 to LL[t,x] do
  inc(c[i+j-1],a[t,x]^[i]*a[t,x]^[j]);
  for i:=1 to LL[t,x]+LL[t,x] do
  begin
    inc(c[i+1],c[i] div 10);
    c[i]:=c[i] mod 10;
  end;
  if c[LL[t,x]+LL[t,x]]<>0 then L:=LL[t,x]+LL[t,x]
  else L:=LL[t,x]+LL[t,x]-1;
  for i:=L downto 1 do
  write(c[i]);
  writeln;
end;

Begin
  read(n);
  read(m);
  if (m>2*n*9)or(odd(m)) then
  begin
    writeln(0);
    exit;
  end;
  m:=m shr 1;
  for j:=0 to 1 do
  for i:=0 to m+1 do
  begin
    new(a[j,i]);
    fillchar(a[j,i]^,sizeof(a[j,i]^),0);
  end;
  for i:=0 to 9 do
  begin
    a[1,i]^[1]:=1;
    LL[1,i]:=1;
  end;
  t:=1;
  t1:=0;
  for i:=2 to n do
  begin
    t1:=t;
    t:=1-t;
    for j:=0 to m+1 do
    fillchar(a[t,j]^,sizeof(a[t,j]^),0);
    fillchar(LL[t],sizeof(LL[t]),0);
    u:=i*9;
    if m<u then u:=m;
    for j:=0 to u do
    begin
      v:=j-9;
      if v<0 then v:=0;
      for k:=v to j do
      go(j,k);
    end;
    LL[t1]:=LL[t];
  end;
  cheng(m);
End.

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.

  Though I think my program is correct, the judger always give me WA,
why?
  Here is my code. I use a longint to save 4 digits:

program U1036;
const
  digits=10000;
type
  bignum=array[1..80] of longint;
var
  f:array[1..2,0..1000] of bignum;
  n,s,i,j,k,l:longint;
  re:array[1..400] of longint;
  ns:string;

  procedure add(p,q:longint);
  var
    i,j:longint;
  begin
    for i:=1 to 80 do begin
      inc(f[2,p,i],f[1,q,i]);
      if f[2,p,i]>digits then begin
        inc(f[2,p,i+1]);
        dec(f[2,p,i],digits);
      end;
    end;
  end;

begin
  readln(n,s);
  if n=0 then begin
    writeln(0);
    halt;
  end;
  fillchar(f,sizeof(F),0);
  for i:=0 to 9 do f[1,i,1]:=1;
  if (n*9*2<s)or odd(s) then begin
    writeln(0);
    halt;
  end;
  s:=s div 2;
  fillchar(f[2],sizeof(f[2]),0);
  for i:=2 to n do begin
    if 9*i>s then l:=s else l:=9*i;
    for j:=0 to 9*i do
      for k:=0 to 9 do
        add(j+k,j);
    if i<>n then begin
      f[1]:=f[2];
      fillchar(f[2],sizeof(f[2]),0);
    end;
  end;
  fillchar(re,sizeof(re),0);
  for i:=1 to 80 do
    for j:=1 to 80 do
      inc(re[i+j-1],f[2,s,i]*f[2,s,j]);
  for i:=1 to 400 do
    if re[i]>digits then begin
      inc(re[i+1],re[i] div digits);
      re[i]:=re[i] mod digits;
    end;
  i:=400;
  while (re[i]=0)and(i>0) do dec(i);
  if i=0 then writeln(0) else begin
    write(re[i]);
    for j:=i-1 downto 1 do begin
      str(re[j],ns);
      while length(ns)<4 do ns:='0'+ns;
      write(ns);
    end;
    writeln;
  end;
end.

My idea is to solve it using DP of course. I have to use large
numbers for the result, unfortunately. Which means, that if I have an
array
50*500*sizeof(large num)
i'll have
25000*sizeof(large num)
large nums have about 100 digits, which is 100 bytes, so
25000*100=2500000=2 500 000 bytes, which is more than 1000K :(
If I use just recursion and do not store the results, I'll get time
limit exceeded.
My idea was to have the large numbers as
struct(=class=record) large {
 char* num;
 int size;
}
and allocate memory enough for each of the digits of every number.
The problem is that in C i have to use mallloc and realloc(I know I
can use new instead of malloc, but realloc is the real problem).
Realloc, however, doesn't work OK on my computer and on TIMUS, as I
have seen it :)) The strange fact is that if I trace the program, it
works fine, and if I run it -> it fails. I have the same problem on
another problem on timus, I do not remember which it was. Maybe
because I am allocating too much memory on too many pieces, which are
very small(a byte per time, about a million of times).

So, I help someone has read that,and that someone is going to help
about
1) What to use to solve the problem?
2) How can I solve the problem with realloc

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.

I have decided(solved) this task. People deciding her(it), shall
advise to take sheet with handle and to touch all variants for
N=1,2,3 And you will see law!!!