This is a problem from SPOJ. I am getting W/A on submission.The sample test case is passing. I am looking for some test-cases where my code will fail. If anyone could help me with that, It will be a huge help.
Ada the Ladybug is playing Game of Divisors against her friend Velvet Mite Vinit. The game has following rules. There is a pile of N stones between them. The player who’s on move can pick at least 1 an at most σ(N) stones (where σ(N) stands for number of divisors of N). Obviously, N changes after each move. The one who won’t get any stones (N == 0) loses.
As Ada the Ladybug is a lady, so she moves first. Can you decide who will be the winner? Assume that both players play optimally.
Input The first line of input will contain 1 ≤ T ≤ 10^5, the number of test-cases.
The next T lines will contain 1 ≤ N ≤ 2*107, the number of stones which are initially in pile.
Output Output the name of winner, so either “Ada” or “Vinit”.
Example Input
8
1
3
5
6
11
1000001
1000000
29
Example Output:
Ada
Vinit
Ada
Ada
Vinit
Vinit
Ada
Ada
CODE :
import java.io.*; public class Main { public static int max_size = 2 * (int)Math.pow(10,7) + 1; public static boolean[] dp = new boolean[max_size]; public static int[] lastPrimeDivisor = new int[max_size]; public static int[] numOfDivisors = new int[max_size]; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); preprocess(); int t = Integer.parseInt(br.readLine()); while(t > 0) { int n = Integer.parseInt(br.readLine()); if(dp[n] == true) System.out.println("Ada"); else System.out.println("Vinit"); t--; } } public static void markLastPrimeDivisor() { for(int i = 0 ; i < max_size ; i++) { lastPrimeDivisor[i] = 1; } for(int i = 2 ; i < max_size ; i += 2) { lastPrimeDivisor[i] = 2; } int o = (int)Math.sqrt(max_size) + 1; for(int i = 3 ; i < max_size; i++) { if(lastPrimeDivisor[i] != 1) { continue; } lastPrimeDivisor[i] = i; if(i <= o) { for(int j = i * i ; j < max_size ; j += 2 * i) { lastPrimeDivisor[j] = i; } } } /*for(int i = 1 ; i < max_size ; i++) System.out.println("last prime of " + i + " is " + lastPrimeDivisor[i]);*/ } public static void countDivisors(int num) { int original = num; int result = 1; int currDivisorCount = 1; int currDivisor = lastPrimeDivisor[num]; int nextDivisor; while(currDivisor != 1) { num = num / currDivisor; nextDivisor = lastPrimeDivisor[num]; if(nextDivisor == currDivisor) { currDivisorCount++; } else { result = result * (currDivisorCount + 1); currDivisorCount = 1; currDivisor = nextDivisor; } } if(num != 1) { result = result * (currDivisorCount + 1); } //System.out.println("result for num : " + original + ", " + result); numOfDivisors[original] = result; } public static void countAllDivisors() { markLastPrimeDivisor(); for(int i = 2 ; i < max_size ; i++) { countDivisors(i); //System.out.println("num of divisors of " + i + " = " + numOfDivisors[i]); } } public static void preprocess() { countAllDivisors(); dp[0] = dp[1] = dp[2] = true; for(int i = 3 ; i < max_size ; i++) { int flag = 0; int limit = numOfDivisors[i]; for(int j = 1 ; j <= limit; j++) { //If for any i - j, we get false,for playing optimally //the current opponent will choose to take j stones out of the //pile as for i - j stones, the other player is not winning. if(dp[i - j] == false) { dp[i] = true; flag = 1; break; } } if(flag == 0) dp[i] = false; } } } 
