import java.io.*; import java.util.*; import java.awt.geom.*; /** * Solution to Weightlifting * * @author vanb */ public class weightlifting_vanb { public Scanner sc; public PrintStream ps; /** This large number will be infinity for us. */ public static final long INFINITY = 10000000000L; /** * Driver. * @throws Exception */ public void doit() throws Exception { sc = new Scanner( System.in ); ps = System.out; int e = sc.nextInt(); int es = sc.nextInt(); int ef = sc.nextInt(); // To explain this solution, let's look at a different, but similar, problem. // Suppose you wanted to find your (unknown) strength s, using a binary search. // // On your first lift, you split the space of possible values in 2. // So, you've got 1 split point, chopping the space into 2 partitions. // // Where in the space you try your second lift is based on the first. // If you succeed, go higher. If you fail, go lower. In either case, // you can ignore the other side. So with 2 lifts you can split the space into 4 partitions, // with 3 split points - one above the first lift, one below. Just standard binary search. // // Likewise, with 3 lifts, you can split the space into 8 partitions with 7 split points, // and so on. // // If e[success]==e[failure], then that's all that's going on in this problem. Unfortunately, // it will not generally be the case that e[success]==e[failure]. So, we've got to figure // out our number of split points (and partitions). // // We'll figure out splits[i], which is the number of split points if you have i energy remaining. // It'll just be the number of splits if you succeed (splits[i-es]) plus the // number of splits if you fail (splits[i-ef]) plus one, for the lift you make right then & there. // Then splits[e] will be the total number of split points for our initial energy e. long splits[] = new long[e+1]; Arrays.fill( splits, 0 ); for( int i=1; i<=e; i++ ) { // Note that these numbers can get big ... REALLY big. Like, overflow big. // So, we'll need to protect against that with a maximum value, which will be, // for all intents and purposes, infinity. splits[i] = Math.min( (i>=es?splits[i-es]:0) + (i>=ef?splits[i-ef]:0) + 1, INFINITY ); } // p is the number of partitions for starting energy e. // We want all of the partitions to be of equal size, so that, // no matter what happens and which path we take, we're as close // as possible to our (unknown) strength s. long p = splits[e]+1; // OK, so this is a little odd, so bear with me. // You can always lift the 25kg bar, so if you're trying to maximize your score, // it seems like you'd always want to save one lift to do that. // But, the problem isn't to maximize your score (I know... counterintuitive) // The problem is to get as close as possible to your unknown strength s. // In other words, to minimize the size of each partition. To do that, saving // a lift for the 25kg bar might not be the best solution. // // Consider the first sample I/O, in which you can only manage one lift. // If you use it to lift the 25kg bar, you get a score of 25. You don't know your strength s. // You might have been able to lift as much as 225kg. So, you could be as much // as 200kg off from s. In this case, d=200. // // Now, suppose instead, you lift at 112.5kg. If you succeed, you get a score of 112.5. // Your unknown strength s could have been as high as 225. so, d=225-112.5=112.5. // If you fail, your score is 0. Your strength can't be 112.5 or higher, // but it could be just a shade under. So d=112.5-0=112.5. // This way, even though you risk a zero score, you minimize d. // // So, which is better? We don't know a priori, so we'll try both and take the best. // If we save a lift for 25kg, then we've got one fewer split points and one fewer partitions, // but our search space is 225-25=200. If we don't, then we use all of our partitions, // we risk a 0 score, and our search space is 225-0=225 ps.printf( "%.6f", Math.abs( Math.min( 200.0/(p-1), 225.0/p ) ) ); ps.println(); // This is for the judges, to make sure that no solution is too close to a rounding cusp. String answer = String.format( "%.8f", Math.abs( Math.min( 200.0/p, 225.0/(p+1) ) ) ); if( answer.endsWith( "50" ) || answer.endsWith( "49" ) ) System.err.println( "PANIC!! " + answer + " is too close to a cusp"); } /** * @param args */ public static void main( String[] args ) throws Exception { new weightlifting_vanb().doit(); } }