document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. import java.util.*;
  2. import java.math.*;
  3.  
  4. public class PrimeCompositeGame {
  5.     boolean [] primes;
  6.     int [] dif;
  7.    public int theOutcome(int N, int K) {
  8.        if(N<3)return 0;
  9.        sieve();//to get the primes
  10.        difBuild();//to build all the differences between index and the closest smaller prime
  11.        int l = firstlose(K);//get the first integer the difference between it and the closest smaller prime is bigger than K
  12.        if(l==-1||l>N){// you win
  13.            return win(N,K);
  14.        }else{//you lose
  15.            return lose(N,K);
  16.        }
  17.    }
  18.    private int lose(int n,int k) {
  19.        int turns=0;
  20.        while(true){
  21.            if(dif[n]==0&&dif[n-1]>k-1)return -1*turns;//if you can\'t move
  22.            if(dif[n]>k)return -1*turns;//if you can\'t move
  23.            if(dif[n]==0)n--;//if you started at a prime
  24.            n=n-dif[n];//get the closest prime
  25.            for (int i = 1; i <= k; i++) {//search if there exist a losing state in range
  26.                if(n-i<0)continue;
  27.                if(dif[n-i]>k)return -1*(turns+2);
  28.            }
  29.            for (int i = 0; i < k; i++) {//get the smallest integer you can get
  30.                if(n-k+i<0)continue;
  31.                if(!primes[n-k+i]){n=n-k+i;break;}
  32.            }
  33.            turns+=2;
  34.        }
  35. }
  36. private int win(int n,int k) {
  37.     int turns=0;
  38.     while(true){
  39.         if(n-3<=k){//no more moves
  40.             return turns+1;
  41.         }
  42.         turns+=2;
  43.         for (int i = 0; i < k; i++) {//get the smallest prime within range then remove one
  44.             if(n-k+i<0)continue;
  45.             if(primes[n-k+i]){n=n-k-1+i;break;}
  46.         }
  47.     }
  48. }
  49. private void sieve() {
  50.     // TODO Auto-generated method stub
  51.     primes=new boolean[500000];
  52.     Arrays.fill(primes, true);
  53.     primes[0]=false;
  54.     primes[1]=false;
  55.     for (int i = 2; i < primes.length; i++) {
  56.         if(primes[2]){
  57.             for (int j = i+i; j < primes.length; j+=i) {
  58.                 primes[j]=false;
  59.             }
  60.         }
  61.     }
  62.    }
  63.    
  64.     private void difBuild(){
  65.         dif=new int[500000];
  66.         for (int i = 2; i < dif.length; i++) {
  67.             if(primes[i])dif[i]=0;
  68.             else dif[i]=dif[i-1]+1;
  69.         }
  70.     }
  71.     private int firstlose(int k){
  72.         for (int i = 4; i < dif.length; i++) {
  73.             if(dif[i]>k)return i;
  74.         }
  75.         return -1;
  76.     }
  77. }
  78.  
');