SHARE
TWEET

Untitled

a guest Oct 12th, 2017 56 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. import java.io.File;
  3. import java.io.IOException;
  4. import java.io.PrintWriter;
  5. import java.util.*;
  6.  
  7. public class Main_Prime_Darts_13245 {
  8.  
  9.     static int dp[], fail = -1 >>> 5;
  10.     static List<Integer> list = new ArrayList<Integer>();
  11.  
  12.     static int rec(int p[], int v) {
  13.         for (int i = 1; i < dp.length; i++) {
  14.             dp[i] = fail;
  15.         }
  16.         for (int i = 0; i <= v; i++) {
  17.             for (int j = 0; j < p.length; j++) {
  18.                 if (p[j] <= i) {
  19.                     int sub = dp[i - p[j]];
  20.                     if (sub != fail && sub + 1 < dp[i]) {
  21.                         dp[i] = sub + 1;
  22.                     }
  23.                 }
  24.             }
  25.         }
  26.         return dp[v];
  27.     }
  28.    
  29.     static int rec2(int[] p, int v){
  30.         if (dp[v] != fail) return dp[v];
  31.        
  32.         for (int prime : p) {
  33.             if (v >= prime) {
  34.                 dp[v] = 1+ ( rec2(p, v - prime));
  35.             }
  36.         }
  37.        
  38.        
  39.        
  40.         return dp[v];
  41.     }
  42.  
  43.     public static void main(String[] args) throws IOException {
  44.         Scanner in = new Scanner(new File("input.txt"));
  45.         PrintWriter out = new PrintWriter(System.out);
  46.         Primes.sieve();
  47.         int tc = in.nextInt();
  48.         while (tc-- > 0) {
  49.             int size = in.nextInt();
  50.             int sum = in.nextInt();
  51.             int[] prime = new int[list.size()];
  52.             for (int i = 0; i < prime.length; i++) {
  53.                 prime[i] = list.get(i);
  54.             }
  55.             int[] p = Arrays.copyOf(prime, size);
  56.             dp = new int[sum + 1];
  57.             Arrays.fill(dp, fail);
  58.             dp[0] = 0;
  59.             out.println(rec2(p, sum));
  60.         }
  61.         out.flush();
  62.     }
  63.  
  64.     static class Primes {
  65.  
  66.         static BitSet bset;
  67.         static int MAX = 50000;
  68.  
  69.         public static void sieve() {
  70.             bset = new BitSet(MAX);
  71.             list.add(1);
  72.             bset.set(2);
  73.             list.add(2);
  74.             for (int j = 3; j < MAX; j += 2) {
  75.                 bset.set(j);
  76.             }
  77.             int sqrt = (int) Math.sqrt(MAX);
  78.             for (int i = 3; i < sqrt; i += 2) {
  79.                 if (bset.get(i)) {
  80.                     for (int j = i * i; j < MAX; j += 2 * i) {
  81.                         bset.clear(j);
  82.                     }
  83.                     list.add(i);
  84.                 }
  85.             }
  86.         }
  87.         //long values start from 4422
  88.  
  89.         public static boolean isPrime(long n) { // n>=0
  90.             if (n < MAX) {
  91.                 return bset.get((int) n);
  92.             }
  93.             int sqrt = (int) Math.sqrt(n);
  94.             for (int i = 2; i <= sqrt; i = bset.nextSetBit(i + 1)) {
  95.                 if (n % i == 0) {
  96.                     return false;
  97.                 }
  98.             }
  99.             return true;
  100.         }
  101.     }
  102.  
  103. }
RAW Paste Data
Top