mountains/BeautifulMountains_artur.java

  1 import java.util.ArrayList;
  2 import java.util.Scanner;
  3 
  4 public class BeautifulMountains_artur {
  5   public static void main(String[] args) throws Exception {
  6     Scanner in = new Scanner(System.in);
  7 
  8     ArrayList<Integer> primes = new ArrayList<Integer>();
  9     boolean[] v = new boolean[30001];
 10     for (int i = 2; i < v.length; i++)
 11       if (!v[i]) {
 12         if (i > 2)
 13           primes.add(i);
 14         for (int j = i * i; j < v.length; j += i)
 15           v[j] = true;
 16       }
 17 
 18     for (int n = in.nextInt(); n != 0; n = in.nextInt()) {
 19       int[] a = new int[n];
 20       for (int i = 0; i < n; i++)
 21         a[i] = in.nextInt();
 22 
 23       long[] l = new long[n], r = new long[n];
 24       long[] lsum = new long[n], rsum = new long[n];
 25       for (int i = 1, j = n - 2; i < n; i++, j--) {
 26         lsum[i] = lsum[i - 1] + a[i - 1];
 27         rsum[j] = rsum[j + 1] + a[j + 1];
 28         l[i] = l[i - 1] + lsum[i];
 29         r[j] = r[j + 1] + rsum[j];
 30       }
 31 
 32       long best = Long.MAX_VALUE;
 33       for (int i = 0; i < n; i++) {
 34         best = Math.min(best, l[i] + r[i]);
 35         if (i + 2 < n)
 36           best = Math.min(best, l[i] + r[i + 2] + a[i + 1]);
 37 
 38         for (int p : primes) {
 39           int j = i + p;
 40           if (j < n) {
 41             long temp = 0;
 42             int k = (i + j) / 2;
 43             temp += r[i] - r[k] - rsum[k] * (k - i);
 44             temp += l[j] - l[k + 1] - lsum[k + 1] * (j - k - 1);
 45 
 46             best = Math.min(best, temp + l[i] + r[j]);
 47 
 48             if (!v[p + 2]) {
 49               if (i > 1)
 50                 best = Math.min(best, temp + r[j] + l[i - 2] + a[i - 1]);
 51               if (j < n - 2)
 52                 best = Math.min(best, temp + l[i] + r[j + 2] + a[j + 1]);
 53               if (!v[p + 4] && i > 1 && j < n - 2)
 54                 best = Math.min(best, temp + l[i - 2] + r[j + 2] + a[i - 1] + a[j + 1]);
 55             }
 56           } else
 57             break;
 58         }
 59       }
 60       System.out.println(best);
 61     }
 62   }
 63 }