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
16 int[] locs = new int[4];
17 int[] borders = new int[5];
18
19
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
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
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
64 genPrimes(MAXN);
65
66
67
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
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
98
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
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
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
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 }