mountains/mountains_vanb.java
1
2 import java.io.*;
3 import java.util.*;
4 import java.awt.geom.*;
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27 public class mountains_vanb
28 {
29 public Scanner sc;
30 public PrintStream ps;
31
32 private static final boolean debugging = false;
33 private static void debug( String message )
34 {
35 if( debugging ) System.out.println( message );
36 }
37
38
39
40
41
42 public void doit() throws Exception
43 {
44 sc = new Scanner( new File( "mountains.judge" ) );
45 ps = new PrintStream( new FileOutputStream( "mountains.vanb" ) );
46
47 int primes[] = new int[30000];
48 int np = 0;
49
50
51 boolean isprime[] = new boolean[31000];
52 Arrays.fill( isprime, true );
53 isprime[0] = false;
54 isprime[1] = false;
55 for( int i=2; i<isprime.length; i++ ) if( isprime[i] )
56 {
57 primes[np++] = i;
58 for( int j=i+i; j<isprime.length; j+=i)
59 {
60 isprime[j] = false;
61 }
62 }
63
64 int mountains[] = new int[30001];
65 long sums[] = new long[30001];
66 long leftcosts[] = new long[30001];
67 long rightcosts[] = new long[30001];
68
69 for(;;)
70 {
71 int n = sc.nextInt();
72 if( n==0 ) break;
73
74 mountains[0] = sc.nextInt();
75 sums[0] = mountains[0];
76 leftcosts[0] = 0;
77 for( int i=1; i<n; i++ )
78 {
79 mountains[i] = sc.nextInt();
80 sums[i] = sums[i-1] + mountains[i];
81 leftcosts[i] = leftcosts[i-1] + sums[i-1];
82 }
83
84 rightcosts[n-1] = 0;
85 for( int i=n-2; i>=0; i-- )
86 {
87 rightcosts[i] = rightcosts[i+1] + sums[n-1] - sums[i];
88 }
89
90 long best = Long.MAX_VALUE;
91
92 for( int i=0; i<n; i++ )
93 {
94
95
96 long cost1 = leftcosts[i] + rightcosts[i];
97 if( cost1<best ) best = cost1;
98
99 if( i<n-2 )
100 {
101 long cost2 = leftcosts[i] + mountains[i+1] + rightcosts[i+2];
102 if( cost2<best ) best = cost2;
103 }
104
105
106 for( int j=1; primes[j]<n-i; j++ )
107 {
108 int p = primes[j];
109
110
111
112 long costP = leftcosts[i] + rightcosts[i+p];
113 int mid = p/2;
114 long rightmove = rightcosts[i] - rightcosts[i+mid+1] - (mid+1)*(sums[n-1] - sums[i+mid]);
115 long leftmove = leftcosts[i+p] - leftcosts[i+mid] - (mid+1)*sums[i+mid];
116 costP += rightmove;
117 costP += leftmove;
118 if( costP<best ) best = costP;
119
120 if( i>1 && isprime[p+2] )
121 {
122
123 long cost2P = costP - leftcosts[i] + leftcosts[i-2] + mountains[i-1];
124 if( cost2P<best ) best = cost2P;
125 }
126 if( i+p<n-2 && isprime[p+2] )
127 {
128
129 long costP2 = costP - rightcosts[i+p] + rightcosts[i+p+2] + mountains[i+p+1];
130 if( costP2<best ) best = costP2;
131 }
132 if( i>1 && i+p<n-2 && isprime[p+2] && isprime[p+4] )
133 {
134
135 long cost2P2 = costP - leftcosts[i] + leftcosts[i-2] + mountains[i-1]
136 - rightcosts[i+p] + rightcosts[i+p+2] + mountains[i+p+1];
137 if( cost2P2<best ) best = cost2P2;
138 }
139 }
140 }
141
142 ps.println( best );
143 }
144 }
145
146
147
148
149 public static void main( String[] args ) throws Exception
150 {
151 long start = System.currentTimeMillis();
152 new mountains_vanb().doit();
153 System.out.println( System.currentTimeMillis() - start );
154 }
155 }