wa4 have test n=1 and some m
if u use dp and u write in your massive some int, when u write, u delete int and create new ints. But if u have n=1, u now answer for every for n=1 and when u use dp its write 0, it enters zero instead of the answer you wrote down, although there should be one in some cells

  Have anybody crash on 3 test?
It's interesting, that my friend decided this problem and on tests with n>50 we have the same answer.

I think that this is too easy problem for 297 points of hardness

it wasted my whole day using string.
then i use array instead of boring string and accepted

I can get the right answer of 50 500,but I can't AC the second test..What's up? What's the data?

Answers for big tests is very big. For example, for test "50 500" answer is "854559745684320697549060368131279814466643179689928095831053239604130293492672614469791533133321".
Don't use long long or int64! Use long numbers (long arithmetic)! (Длинная арифметика)

2 4
2 6
2 8
4 2
4 4
4 6
4 8

10 0
1

2 1
0

30 95
0

3 4
36

3 6
100

10 30
1657615050256

15 30
5988336077235600

20 100
475696100826892995150152084506564

50 300
3660144008320861404705392514284143308670326732628084621145897204106027006076468826991924409

The value of N is <= 50, so we are talking about a 100 digit number atmost.....how then the upper limit of S is 1000.....shouldn't it be 900.....or are we supposed to return 0 when (2*N*9) < S.

Am I missing something ?????

Edited by author 10.11.2013 01:07

Nevermind.....I solved it.....

Few useful insights :-

(i) if S > (2*9*N) output 0;
(ii) if S = 0 output 1; (otherwise you would get WA for test 5).

Edited by author 10.11.2013 02:27

The correct answer for test 3 4
is 36. May be it will help someone

Big number really?

Please help me, i don't understand what is wrong with the code below


import java.math.BigInteger;
import java.io.*;
import java.util.*;

public class LuckyTickets
{


    public static void main(String[] args)
    {

        int N,S;
        BigInteger F[][] = new BigInteger[51][];

        for(int i = 0; i <= 50; i++)
            F[i]= new BigInteger[1001];

        Scanner scanner= new Scanner(System.in);
        try
        {
            N= scanner.nextInt();
            S= scanner.nextInt();


            for(int j= 0; j <= N; j++)
                for(int i= 0; i <= S; i++)
                    F[j][i]= new BigInteger("0");

            for(int j= 1; j <= N; j++)
                F[j][0] = BigInteger.ONE;

            for(int i= 1; i < 10; i++)
                F[1][i] = BigInteger.ONE;

            for(int i= 2; i <= N; i++)
                for(int k= 1; k <= S; k++)
                {
                    for(int j= 0; j <= 9 && j <= k; j++)
                        F[i][k]= F[i][k].add(F[i-1][k-j]);
                }

            // there are F[N][S/2] * F[N][S/2] different tickets
            System.out.println(F[N][S/2].multiply(F[N][S/2]));

//            for(int j= 0; j <= N; j++){
//                for(int i= 0; i <= S; i++)
//                    System.out.print(F[j][i]+ " ");
//                System.out.println("");
//            }

        }
        catch(InputMismatchException e)
        {
            System.out.println("Mismatch exception " + e);
        }

    }
}

New tests were added. 146 authors lost AC after rejudge.

test 2: s%2!=0 so answer is 0
test 5: S is 0 so answer is 1

Good luck :)

My program works correctly on all tests from the forum:

50 500
--> 854559745684320697549060368131279814466643179689928095831053239604130293492672614469791533133321

50 450
-->
3834688188199309756675466732967588185862422492337212276545580039517258085033387305291001857619600

10 2
-->
100

50 1000
-->
0

3 1
-->
0

50 250
-->
41409732703108026572448942476041207839411119408173570127621420289526490759097327483136

50 300
-->
3660144008320861404705392514284143308670326732628084621145897204106027006076468826991924409

5 10
-->
15876

50 896
-->
1625625

10 10
-->
4008004

49 2
-->
2401

1 20
-->
0

50 0
-->
1

, but I got WA#1! I used DP and long arithm.
What it can be caused by?

Edited by author 08.04.2010 05:42

Edited by author 08.04.2010 05:43

type
 sl=array[1..150] of longint;
var
 i,j,k,l,n,m,s:longint;
 f:array[0..50,-10..1000] of sl;
 u:sl;
function gjc(a:sl):sl;
var
  i,t:longint;
  tmp:sl;
begin
  for i:=120 downto 1 do
    if a[i]<>0 then break;
  t:=i;
  fillchar(tmp,sizeof(tmp),0);
  for i:=1 to t do
    for j:=1 to t do
      inc(tmp[i+j-1],a[i]*a[j]);
  for i:=1 downto 120 do
  begin
    tmp[i+1]:=tmp[i+1]+tmp[i] div 10000;
    tmp[i]:=tmp[i] mod 10000;
  end;
  exit(tmp);
end;


procedure gjj(b:sl;var a:sl);
var
 i,j,k,l:longint;

begin
 for i:=1 to 120 do
  a[i]:=a[i]+b[i];
 for j:=1 to 120 do
  begin
   inc(a[j+1],a[j] div 10000);
   a[j]:=a[j] mod 10000;
  end;
end;

procedure printgj(a:sl);
var
 i,j,k,l,len:longint;
 st:string;
begin
 i:=120;
 while (i>0)and(a[i]=0) do dec(i);
 if i=0 then BEGIN writeln(0);exit;end;
 len:=i-1;
 write(a[len+1]);
 for i:=len-1 downto 1 do
  begin
   str(a[i],st);
   while length(st)<4 do insert('0',st,1);
   write(st);
  end;
end;

begin
 readln(n,s);
 if (n=1)and(s<=9) then begin writeln(1);halt; end;
 if s mod 2=1 then begin writeln(0);halt; end;
 f[0,0][1]:=1;
 for i:=1 to n do
  for j:=0 to s shr 1 do
   for k:=0 to 9 do
    begin
     gjj(f[i-1,j-k],f[i,j]);
    end;
 l:=s shr 1;
 u:=(gjc(f[n,l]));
 printgj(u);
end.

Edited by author 07.01.2010 10:17

I use java BigInteger and get WA#7
I use formula f(n,k)=f(n-1,k)+f(n-1,k-1)+...+f(n-1,k-9)
if you see it is wrong,please help

Edited by author 25.01.2009 13:43

maybe it will be more interesting for me but....


...anyway, can't function be array, record, set in Pascal?

thanks.



Edited by author 21.12.2007 13:28

my program works correctly on all the tests from the forum...
//I use long arithmetic and DP