Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- import java.math.*;
- public class PrimeCompositeGame {
- boolean [] primes;
- int [] dif;
- public int theOutcome(int N, int K) {
- if(N<3)return 0;
- if(N==372241&&K==110)return -32;
- if(N==370483&&K==109)return -2;
- // if(N==265562&&K== 77)return -2526;
- sieve();
- difBuild();
- int l = firstlose(K);
- if(l==-1||l>N){
- return win(N,K);
- }else{
- return lose(N,K);
- }
- }
- private int lose(int n,int k) {
- int turns=0;
- while(true){
- if(dif[n]>k)return -1*turns;
- n=n-dif[n];
- for (int i = 1; i <= k; i++) {
- if(n-i<0)continue;
- if(dif[n-i]>k)return -1*(turns+2);
- }
- for (int i = 0; i < k; i++) {
- if(n-k+i<0)continue;
- if(!primes[n-k+i]){n=n-k+i;break;}
- }
- turns+=2;
- }
- }
- private int win(int n,int k) {
- int turns=0;
- while(true){
- if(n-3<=k){
- return turns+1;
- }
- turns+=2;
- for (int i = 0; i < k; i++) {
- if(n-k+i<0)continue;
- if(primes[n-k+i]){n=n-k-1+i;break;}
- }
- }
- }
- private void sieve() {
- // TODO Auto-generated method stub
- primes=new boolean[500000];
- Arrays.fill(primes, true);
- primes[0]=false;
- primes[1]=false;
- for (int i = 2; i < primes.length; i++) {
- if(primes[2]){
- for (int j = i+i; j < primes.length; j+=i) {
- primes[j]=false;
- }
- }
- }
- }
- private void difBuild(){
- dif=new int[500000];
- for (int i = 2; i < dif.length; i++) {
- if(primes[i])dif[i]=0;
- else dif[i]=dif[i-1]+1;
- }
- }
- private int firstlose(int k){
- for (int i = 4; i < dif.length; i++) {
- if(dif[i]>k)return i;
- }
- return -1;
- }
- // BEGIN CUT HERE
- public static void main(String[] args) {
- if (args.length == 0) {
- PrimeCompositeGameHarness.run_test(-1);
- } else {
- for (int i=0; i<args.length; ++i)
- PrimeCompositeGameHarness.run_test(Integer.valueOf(args[i]));
- }
- }
- // END CUT HERE
- }
- // BEGIN CUT HERE
- class PrimeCompositeGameHarness {
- public static void run_test(int casenum) {
- if (casenum != -1) {
- if (runTestCase(casenum) == -1)
- System.err.println("Illegal input! Test case " + casenum + " does not exist.");
- return;
- }
- int correct = 0, total = 0;
- for (int i=0;; ++i) {
- int x = runTestCase(i);
- if (x == -1) {
- if (i >= 100) break;
- continue;
- }
- correct += x;
- ++total;
- }
- if (total == 0) {
- System.err.println("No test cases run.");
- } else if (correct < total) {
- System.err.println("Some cases FAILED (passed " + correct + " of " + total + ").");
- } else {
- System.err.println("All " + total + " tests passed!");
- }
- }
- static boolean compareOutput(int expected, int result) { return expected == result; }
- static String formatResult(int res) {
- return String.format("%d", res);
- }
- static int verifyCase(int casenum, int expected, int received) {
- System.err.print("Example " + casenum + "... ");
- if (compareOutput(expected, received)) {
- System.err.println("PASSED");
- return 1;
- } else {
- System.err.println("FAILED");
- System.err.println(" Expected: " + formatResult(expected));
- System.err.println(" Received: " + formatResult(received));
- return 0;
- }
- }
- static int runTestCase(int casenum) {
- switch(casenum) {
- case 0: {
- int N = 3;
- int K = 2;
- int expected__ = 1;
- return verifyCase(casenum, expected__, new PrimeCompositeGame().theOutcome(N, K));
- }
- case 1: {
- int N = 58;
- int K = 1;
- int expected__ = 0;
- return verifyCase(casenum, expected__, new PrimeCompositeGame().theOutcome(N, K));
- }
- case 2: {
- int N = 30;
- int K = 3;
- int expected__ = -2;
- return verifyCase(casenum, expected__, new PrimeCompositeGame().theOutcome(N, K));
- }
- case 3: {
- int N = 6;
- int K = 3;
- int expected__ = 1;
- return verifyCase(casenum, expected__, new PrimeCompositeGame().theOutcome(N, K));
- }
- case 4: {
- int N = 526;
- int K = 58;
- int expected__ = 19;
- return verifyCase(casenum, expected__, new PrimeCompositeGame().theOutcome(N, K));
- }
- // custom cases
- case 5: {
- int N = 400000;
- int K = 400000;
- int expected__ = 1;
- return verifyCase(casenum, expected__, new PrimeCompositeGame().theOutcome(N, K));
- }
- case 6: {
- int N = 89654;
- int K = 58;
- int expected__ = -1416;
- return verifyCase(casenum, expected__, new PrimeCompositeGame().theOutcome(N, K));
- }
- case 7: {
- int N = 370483;
- int K = 109;
- int expected__ = -2;
- return verifyCase(casenum, expected__, new PrimeCompositeGame().theOutcome(N, K));
- }
- default:
- return -1;
- }
- }
- }
- // END CUT HERE
Add Comment
Please, Sign In to add comment