mountains/mountains_vanb.java

  1 
  2 import java.io.*;
  3 import java.util.*;
  4 import java.awt.geom.*;
  5 
  6 /**
  7  * Solution to Beautiful Mountains
  8  * 
  9  * Stack blocks a prime distance apart. ALL stacks must be a prime distance
 10  * from ALL other stacks, NOT just adjacent stacks! 
 11  * 
 12  * Well, there are only 5 possibilities:
 13  * Case 1: All the blocks are in a single stack
 14  * Case P: The blocks are in exactly 2 stacks, a prime number distance apart.
 15  * Case 2P: The blocks are in three stacks: the first two 2 apart, and the last one a prime distance from there,
 16  *          where prime+2 is also prime.
 17  * Case P2: The blocks are in three stacks: the first a prime apart, and the last one 2 from there,
 18  *          where prime+2 is also prime.
 19  * Case 2P2: The blocks are in four stacks, distance 2, then a prime, then 2,
 20  *           where prime+2 and prime+4 are also prime.
 21  *           
 22  * There can't be any other combos. Consider P1>2 and P2>2, both prime. 
 23  * Then P1 and P2 are both odd, so P1+P2 is even, and thus not prime.
 24  * 
 25  * @author vanb
 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      * Driver.
 40      * @throws Exception
 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         // Use the Sieve of Eratosthenes to get primes
 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                 // First, lump them all at the same place: i;
 95                 // Case 1
 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                 // Look for prime diffs >2
106                 for( int j=1; primes[j]<n-i; j++ ) 
107                 {
108                     int p = primes[j];
109                     
110                     // 2 piles, a prime distance apart
111                     // Case P
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                         // Case 2P
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                         // Case P2
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                         // Case 2P2
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      * @param args
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 }