import java.io.*; import java.util.*; import java.awt.geom.*; /** * Solution to Sunday Drive. * * @author vanb */ public class sundaydrive { public Scanner sc; public PrintStream ps; public static final int MAX_SEGMENTS = 100000; public static final int MAX_LANES = 10; // Lengths (or Radii) of the segments public int lengths[] = new int[MAX_SEGMENTS+1]; // 'S', 'L' or 'R', depending on the type of the segment. public char types[] = new char[MAX_SEGMENTS+1]; // best[i][j] will be the least distance it takes to drive from the // beginning of the highway to the end of segment i, ending up in lane j. public double best[][] = new double[MAX_SEGMENTS+1][MAX_LANES]; /** * Driver. * @throws Exception */ public void doit() throws Exception { sc = new Scanner( new File( "sundaydrive.judge" ) ); ps = System.out; // new PrintStream( new FileOutputStream( "sundaydrive.solution" ) ); for(;;) { int n = sc.nextInt(); int m = sc.nextInt(); if( n==0 ) break; // Read in segment info, initialize best[][] // To save confusion, we'll index the segments from 1 instead of the // usual 0. So, lengths[1] corresponds to the first segment. // best[0][j] will correspond to starting in lane j. Arrays.fill( best[0], 0.0 ); for( int i=0; i" ); } } } // Go through all of the lanes at the end of the highway, // see which has the least distance. double least = Double.MAX_VALUE; for( int j=0; j