The Java Program: H_robot/robotchallenge.java

  1 import java.io.*;
  2 import java.util.*;
  3 import java.awt.*;
  4 import java.awt.geom.*;
  5 import java.text.*;
  6 import java.math.*;
  7 
  8 /**
  9  * Solution to Robot Challenge using Dynamic Programming
 10  */
 11 class robotchallenge
 12 {
 13     public Scanner sc;
 14     public PrintStream ps;
 15 
 16     public String toString()
 17     {
 18         return "robotchallenge";
 19     }
 20 
 21     /**
 22      * The main method
 23      */
 24     public void doit() throws Exception
 25     {
 26         sc = new Scanner( System.in ); // new Scanner( new File( "robotchallenge.judge" ) );
 27         ps = System.out; // new PrintStream( new FileOutputStream( "robotchallenge.solution" ) );
 28         for(;;)
 29         {
 30                 // Read in n, exit if done
 31             int n = sc.nextInt();
 32             if( n==0 ) break;
 33 
 34             // We're going to add 2 points to the input.
 35             // The start (0,0) and the end (100,100)
 36             n += 2;
 37             int xs[] = new int[n];
 38             int ys[] = new int[n];
 39             int penalties[] = new int[n];
 40 
 41             // The start will be the first point, with a practically infinite penalty
 42             xs[0] = 0;
 43             ys[0] = 0;
 44             penalties[0] = 1000000000;
 45 
 46             // Read in the target points
 47             for( int i=1; i<n-1; i++ )
 48             {
 49                 xs[i] = sc.nextInt();
 50                 ys[i] = sc.nextInt();
 51                 penalties[i] = sc.nextInt();
 52             }
 53 
 54             // The end will be the last point, with a practically infinite penalty
 55             xs[n-1] = 100;
 56             ys[n-1] = 100;
 57             penalties[n-1] = 100000000;
 58 
 59             // best[i] is the best possible score for the rest of the 
 60             // course if we stop at point i
 61             double best[] = new double[n];
 62 
 63             // It costs 1 second to stop at the final point (100,100)
 64             best[n-1] = 1.0;
 65 
 66             // Simple 1d Dynamic Programming
 67             for( int i=n-2; i>=0; i-- )
 68             {
 69                 // Keep a running total of the penalties
 70                 int penalty = 0;
 71                 
 72                 // This is the worst possible value for best[i]
 73                 best[i] = Double.MAX_VALUE;
 74                 
 75                 // What if we go straight from Target Point i to Target Point j?
 76                 for( int j=i+1; j<n; j++ )
 77                 {
 78                     // Since the robot moves at 1 m/s, the distance (in meters)
 79                     // is the same as the time (in seconds)
 80                     int dx = xs[j] - xs[i];
 81                     int dy = ys[j] - ys[i];
 82                     double distance = Math.sqrt( dx*dx + dy*dy );
 83 
 84                     // Cost for stopping at i, then going to j is
 85                     //     1.0 (for the one second stop at i)
 86                     //   + distance (from i to j)
 87                     //   + penalty (for skipping points between i and j)
 88                     //   + best[j] (the best we can do for the rest of the course stopping at j)
 89                     double cost = 1.0 + distance + penalty + best[j];
 90                     if( cost<best[i] ) best[i] = cost;
 91 
 92                     // OK, we're done with j.
 93                     // So, Add in the penalty for skipping j.
 94                     penalty += penalties[j];
 95 
 96                     // Break out if it's too big. The penalty will only increase,
 97                     // and if it gets too large, it can't possibly lead to a better cost.
 98                     // Why the +3.0? Look at how 'cost' is computed.
 99                     // We know 'penalty' will get 1 added to it (for the 1 second stop)
100                     // and we know the points are unique, so the shortest possible
101                     // distance is 1, and we know that best[j] will be at least 1.
102                     if( penalty+3.0 >= best[i] ) break;
103                 }
104             }
105 
106             // So, the answer is the best possible score from the start through the course.
107             // We treated the start point (0,0) just like any other point - that means we
108             // figured in stopping there for 1 second. But, that's not right - we shouldn't
109             // stop at the starting spot at all. So, our answer is exactly 1 second too high.
110             ps.printf( "%.3f", best[0]-1.0 );
111             ps.println();
112         }
113     }
114     
115     public static Random random = new Random();
116     
117     public static void shuffle( Point a[] )
118     {
119         for( int i=0; i<a.length; i++ )
120         {
121                 int j = random.nextInt( a.length );
122                 Point p = a[i];
123                 a[i] = a[j];
124                 a[j] = p;
125         }
126     }
127     
128     public static double distance( Point p1, Point p2 )
129     {
130         int dx = p1.x - p2.x;
131         int dy = p1.y - p2.y;
132         return Math.sqrt( dx*dx + dy*dy );
133     }
134 
135         public static void main(String[] args) throws Exception
136         {
137                 /*
138                 // An array of points for shuffling
139                 Point a[] = new Point[99*99];
140                 int k=0;
141                 for( int x=1; x<=99; x++ ) for( int y=1; y<=99; y++ )
142                 {
143                     a[k++] = new Point( x, y ); 
144                 }
145                 
146                 // Snake-like walk, minimizing distance between points
147                 Point snake[] = new Point[99*99];
148                 k=0;
149                 for( int x=1; x<=99; x+= 2 )
150                 {
151                     for( int y=1; y<=99; y++ )
152                     {
153                         snake[k++] = new Point( x, y );
154                     }
155                     if( x<99 ) for( int y=99; y>=1; y-- )
156                     {
157                         snake[k++] = new Point( x+1, y );
158                     }
159                 }
160                 
161                 // Cross walk, crossing the arena as many times as possible
162                 Point cross[] = new Point[99*99];
163                 k = 0;
164                 int dn = snake.length-1;
165                 int up = 0;
166                 while( k<cross.length )
167                 {
168                         if( k%2==0 )
169                         {
170                             cross[k++] = snake[dn--];
171                         }
172                         else
173                         {
174                             cross[k++] = snake[up++];
175                         }
176                 }
177                 
178                 // Snake, penalty=1
179                 System.out.println( 1000 );
180                 for( int i=0; i<1000; i++ )
181                 {
182                     System.out.println( snake[i].x + " " + snake[i].y + " 1" ); 
183                 }
184                 // Snake, penalty=50
185                 System.out.println( 1000 );
186                 for( int i=0; i<1000; i++ )
187                 {
188                     System.out.println( snake[i].x + " " + snake[i].y + " 50" );        
189                 }
190                 // Snake, penalty=100
191                 System.out.println( 1000 );
192                 for( int i=0; i<1000; i++ )
193                 {
194                     System.out.println( snake[i].x + " " + snake[i].y + " 100" );       
195                 }
196                 // Snake, penalty=random
197                 System.out.println( 1000 );
198                 for( int i=0; i<1000; i++ )
199                 {
200                     System.out.println( snake[i].x + " " + snake[i].y + " " + (random.nextInt(100)+1)); 
201                 }
202                 
203                 // Cross, penalty=1
204                 System.out.println( 1000 );
205                 for( int i=0; i<1000; i++ )
206                 {
207                     System.out.println( cross[i].x + " " + cross[i].y + " 1" ); 
208                 }
209                 // Cross, penalty=50
210                 System.out.println( 1000 );
211                 for( int i=0; i<1000; i++ )
212                 {
213                     System.out.println( cross[i].x + " " + cross[i].y + " 50" );        
214                 }
215                 // Cross, penalty=100
216                 System.out.println( 1000 );
217                 for( int i=0; i<1000; i++ )
218                 {
219                     System.out.println( cross[i].x + " " + cross[i].y + " 100" );       
220                 }
221                 // Cross, penalty=random
222                 System.out.println( 1000 );
223                 for( int i=0; i<1000; i++ )
224                 {
225                     System.out.println( cross[i].x + " " + cross[i].y + " " + (random.nextInt(100)+1)); 
226                 }
227                 
228                 // Max number, penalty 1, order random
229                 shuffle(a);
230                 System.out.println( 1000 );
231                 for( int i=0; i<1000; i++ )
232                 {
233                         System.out.println( a[i].x + " " + a[i].y + " 1" );
234                 }
235                 
236                 // Max number, penalty 100, order random
237                 shuffle(a);
238                 System.out.println( 1000 );
239                 for( int i=0; i<1000; i++ )
240                 {
241                         System.out.println( a[i].x + " " + a[i].y + " 100" );
242                 }
243                 
244                 // Max number, penalty 50, order random
245                 shuffle(a);
246                 System.out.println( 1000 );
247                 for( int i=0; i<1000; i++ )
248                 {
249                         System.out.println( a[i].x + " " + a[i].y + " 50" );
250                 }
251                 
252                 // Max number, penalty random, order random
253                 shuffle(a);
254                 System.out.println( 1000 );
255                 for( int i=0; i<1000; i++ )
256                 {
257                         System.out.println( a[i].x + " " + a[i].y + " " + (random.nextInt(100)+1) );
258                 }
259                 
260                 // Ten more random cases
261                 for( k=0; k<10; k++ )
262                 {
263                         int n = random.nextInt( 1000 ) + 1;
264                         shuffle( a );
265                         System.out.println( n );
266                         for( int i=0; i<n; i++ )
267                         {
268                                 System.out.println( a[i].x + " " + a[i].y + " " + (random.nextInt(100)+1) );
269                         }
270                 }
271         */
272                 long starttime = System.currentTimeMillis();
273                 new robotchallenge().doit();
274                 System.out.println( System.currentTimeMillis() - starttime );
275 
276         }
277 }