Guest User

Untitled

a guest
Dec 15th, 2017
103
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.41 KB | None | 0 0
  1. import java.io.*;
  2.  
  3. public class Main
  4. {
  5. public static int max_size = 2 * (int)Math.pow(10,7) + 1;
  6. public static boolean[] dp = new boolean[max_size];
  7. public static int[] lastPrimeDivisor = new int[max_size];
  8. public static int[] numOfDivisors = new int[max_size];
  9. public static void main(String[] args) throws IOException
  10. {
  11. BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  12. preprocess();
  13. int t = Integer.parseInt(br.readLine());
  14. while(t > 0)
  15. {
  16. int n = Integer.parseInt(br.readLine());
  17. if(dp[n] == true)
  18. System.out.println("Ada");
  19. else
  20. System.out.println("Vinit");
  21. t--;
  22. }
  23. }
  24. public static void markLastPrimeDivisor()
  25. {
  26. for(int i = 0 ; i < max_size ; i++)
  27. {
  28. lastPrimeDivisor[i] = 1;
  29. }
  30. for(int i = 2 ; i < max_size ; i += 2)
  31. {
  32. lastPrimeDivisor[i] = 2;
  33. }
  34. int o = (int)Math.sqrt(max_size) + 1;
  35. for(int i = 3 ; i < max_size; i++)
  36. {
  37. if(lastPrimeDivisor[i] != 1)
  38. {
  39. continue;
  40. }
  41. lastPrimeDivisor[i] = i;
  42. if(i <= o)
  43. {
  44. for(int j = i * i ; j < max_size ; j += 2 * i)
  45. {
  46. lastPrimeDivisor[j] = i;
  47. }
  48. }
  49. }
  50. /*for(int i = 1 ; i < max_size ; i++)
  51. System.out.println("last prime of " + i + " is " + lastPrimeDivisor[i]);*/
  52. }
  53.  
  54. public static void countDivisors(int num)
  55. {
  56. int original = num;
  57. int result = 1;
  58. int currDivisorCount = 1;
  59. int currDivisor = lastPrimeDivisor[num];
  60. int nextDivisor;
  61. while(currDivisor != 1)
  62. {
  63. num = num / currDivisor;
  64. nextDivisor = lastPrimeDivisor[num];
  65. if(nextDivisor == currDivisor)
  66. {
  67. currDivisorCount++;
  68. }
  69. else
  70. {
  71. result = result * (currDivisorCount + 1);
  72. currDivisorCount = 1;
  73. currDivisor = nextDivisor;
  74. }
  75. }
  76. if(num != 1)
  77. {
  78. result = result * (currDivisorCount + 1);
  79. }
  80. //System.out.println("result for num : " + original + ", " + result);
  81. numOfDivisors[original] = result;
  82. }
  83.  
  84. public static void countAllDivisors()
  85. {
  86. markLastPrimeDivisor();
  87. for(int i = 2 ; i < max_size ; i++)
  88. {
  89. countDivisors(i);
  90. //System.out.println("num of divisors of " + i + " = " + numOfDivisors[i]);
  91. }
  92. }
  93.  
  94.  
  95. public static void preprocess()
  96. {
  97. countAllDivisors();
  98. dp[0] = dp[1] = dp[2] = true;
  99. for(int i = 3 ; i < max_size ; i++)
  100. {
  101. int flag = 0;
  102. int limit = numOfDivisors[i];
  103. for(int j = 1 ; j <= limit; j++)
  104. {
  105. //If for any i - j, we get false,for playing optimally
  106. //the current opponent will choose to take j stones out of the
  107. //pile as for i - j stones, the other player is not winning.
  108. if(dp[i - j] == false)
  109. {
  110. dp[i] = true;
  111. flag = 1;
  112. break;
  113. }
  114. }
  115. if(flag == 0)
  116. dp[i] = false;
  117. }
  118.  
  119. }
  120. }
Add Comment
Please, Sign In to add comment