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

why my program gets WA at 2
Posted by subtlebear 26 Nov 2011 15:06

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);
        }

    }
}
Re: why my program gets WA at 2
Posted by DR. Zhihua Lai 14 Dec 2011 03:54
you don't need 2-dimension F[][], just only using one-dimension BigInteger array (in your case, F[]) is enough.

for(int j= 0; j <= 9 && j <= k; j++)  change this to for(int j= 1; j <= 9 && j <= k; j++)

check answer '0' at the begining for two cases:  S is odd or S > 18 * n

second dimension of F is [s + 1] instead of 1001 which kills memory..

I got accepted using Java biginteger as well, and I create the array of below:

BigInteger []f = new BigInteger[s + 1];

That is it!