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 }