Timus : 1036 (Lucky Tickets)



// http://acm.timus.ru/problem.aspx?space=1&num=1036
// Runtime: 0.093s
// Tag: BigInteger, Dp

import java.math.BigInteger;
import java.util.Scanner;
import javax.swing.JFrame;

/**
 *
 * @author Shahab
 */
public class Main{

    static BigInteger memo [] [] = new BigInteger [50 + 3] [1000 + 3];

    public static void main (String [] args)
    {
        Scanner input = new Scanner(System.in);


        int n = input.nextInt();
        int s = input.nextInt();

        if ( s % 2 == 1 ) System.out.println("0");
        else {
            reset();
            BigInteger p = cntTheWays (n, s / 2);
            System.out.println(p.multiply(p));
        }
    }

    public static BigInteger cntTheWays (int n, int s) {
        if ( s < 0 ) return BigInteger.ZERO;
        if ( n == 0 ) {
            if ( s == 0 ) return BigInteger.ONE;
            return BigInteger.ZERO;
        }

        if ( memo [n] [s].compareTo(BigInteger.valueOf(-1)) != 0 ) return memo [n] [s];

        BigInteger ret = BigInteger.ZERO;

        for ( int i = 0; i < 10; i++ )
            ret = ret.add(cntTheWays(n - 1, s - i));

        return memo [n] [s] = ret;
    }

    public static void reset () {
        for ( int i = 0; i < 53; i++ )
            for ( int j = 0; j < 1003; j++ ) memo [i] [j] = BigInteger.valueOf(-1);
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s