mountains/BeautifulMountains.java

  1 import java.io.File;
  2 import java.io.PrintStream;
  3 import java.util.ArrayList;
  4 import java.util.Arrays;
  5 import java.util.Collections;
  6 import java.util.Scanner;
  7 
  8 public class BeautifulMountains {
  9   public static void main(String[] args) throws Exception {
 10     new BeautifulMountains(new Scanner(new File("mountains.in")));
 11   }
 12 
 13   int MAXN = 30000;
 14 
 15   // The mountain locations and range borders
 16   int[] locs = new int[4];
 17   int[] borders = new int[5];
 18 
 19   // Precomputation
 20   int N;
 21   long[] countLeft, countRight;
 22   long[] sumLeft, sumRight;
 23 
 24   boolean[] isPrime;
 25   ArrayList<Integer> primes;
 26 
 27   void genPrimes(int n) {
 28     primes = new ArrayList<Integer>();
 29     isPrime = new boolean[n + 1];
 30     Arrays.fill(isPrime, true);
 31     isPrime[0] = isPrime[1] = false;
 32     for (int i = 0; i <= n; i++)
 33       if (isPrime[i]) {
 34         primes.add(i);
 35         if (i * 1L * i <= n)
 36           for (int j = i * i; j <= n; j += i)
 37             isPrime[j] = false;
 38       }
 39   }
 40 
 41   // Move all the land in interval [i,j] inclusive to mountain k.
 42   long calcSum(int i, int j, int k) {
 43     long costLeft = sumLeft[k + 1] - sumLeft[i + 1] - countLeft[i] * (k - i);
 44     long costRight = sumRight[k] - sumRight[j] - countRight[j + 1] * (j - k);
 45     return costLeft + costRight;
 46   }
 47 
 48   long calcCost(int M) {
 49     // Locations i covers range [borders[i]+1, borders[i+1]], inclusive.
 50     borders[0] = -1;
 51     for (int i = 0; i < (M - 1); i++)
 52       borders[i + 1] = (locs[i] + locs[i + 1]) / 2;
 53     borders[M] = N - 1;
 54 
 55     long res = 0;
 56     for (int i = 0; i < M; i++)
 57       res += calcSum(borders[i] + 1, borders[i + 1], locs[i]);
 58     return res;
 59   }
 60 
 61   public BeautifulMountains(Scanner in) throws Exception {
 62     PrintStream out = new PrintStream(new File("ans"));
 63     // First generate all primes up to MAXN+8. Just to pad things a little.
 64     genPrimes(MAXN);
 65 
 66     // Precompute all the spacing values up to MAXN using those primes.
 67     // These are all the spacings that make sense for the restriction.
 68     ArrayList<Layout> layouts = new ArrayList<Layout>();
 69     layouts.add(new Layout(new int[] {}));
 70     for (int p : primes) {
 71       if (p > MAXN)
 72         break;
 73       layouts.add(new Layout(new int[] { p }));
 74 
 75       if (p + 2 > MAXN)
 76         continue;
 77       if (!isPrime[p + 2])
 78         continue;
 79       layouts.add(new Layout(new int[] { 2, p }));
 80       layouts.add(new Layout(new int[] { p, 2 }));
 81 
 82       if (p + 4 > MAXN)
 83         continue;
 84       if (!isPrime[p + 4])
 85         continue;
 86       layouts.add(new Layout(new int[] { 2, p, 2 }));
 87     }
 88 
 89     // Sort the layouts by the size they take up. This is to break out early.
 90     Collections.sort(layouts);
 91 
 92     for (N = in.nextInt(); N != 0; N = in.nextInt()) {
 93       int[] vs = new int[N];
 94       for (int i = 0; i < N; i++)
 95         vs[i] = in.nextInt();
 96 
 97       // Count the number of chunks of dirt left and right of i including i.
 98       // This value is offset for convenience in calculating the interval.
 99       countLeft = new long[N + 1];
100       countRight = new long[N + 1];
101       for (int i = 0; i < N; i++)
102         countLeft[i + 1] = countLeft[i] + vs[i];
103       for (int i = N - 1; i >= 0; i--)
104         countRight[i] = countRight[i + 1] + vs[i];
105 
106       // Precompute the sum of distances to reach i
107       sumLeft = new long[N + 1];
108       sumRight = new long[N + 1];
109       for (int i = 0; i < N; i++)
110         sumLeft[i + 1] = sumLeft[i] + countLeft[i];
111       for (int i = N - 1; i >= 0; i--)
112         sumRight[i] = sumRight[i + 1] + countRight[i + 1];
113 
114       long res = Long.MAX_VALUE;
115       for (int i = 0; i < N; i++) {
116         for (Layout cur : layouts) {
117           if (i + cur.width >= N)
118             break;
119 
120           // Save the locations
121           int sum = i, ptr = 0;
122           for (int s : cur.space) {
123             locs[ptr++] = sum;
124             sum += s;
125           }
126           locs[ptr] = sum;
127 
128           long rr = calcCost(cur.N);
129           res = Math.min(res, rr);
130         }
131       }
132       out.println(res);
133     }
134   }
135 
136 }
137 
138 class Layout implements Comparable<Layout> {
139   int N, width;
140   int[] space;
141 
142   // Layout from spaces
143   public Layout(int[] ss) {
144     space = ss;
145     N = space.length + 1;
146     width = 0;
147     for (int i = 0; i < space.length; i++)
148       width += space[i];
149   }
150 
151   public int compareTo(Layout rhs) {
152     return width - rhs.width;
153   }
154 }