Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-04-05SRM347 (Practice)

SRM 347 FlightScheduler

|  SRM 347 FlightScheduler - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 347 FlightScheduler - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=7584

  • 問題文が正しく読めず、editorialを読むまで意味不明だった
  • 式変形して1回のフライトでR飛ぶときの必要燃料を求める。
    • n回に分けて飛行する場合の必要燃料を考えた時最適な回数を三分探索で探す。
public class FlightScheduler {
	int em;
	int k;
	
	public double ff(double r) {
		return 1.0d * em * (Math.pow(Math.E, (r / k)) - 1);
	}
	
	public double minimizeFuel(int distance, int K, int emptyMass, int takeoffFuel) {
		em = emptyMass;
		k = K;
		
		long tf = takeoffFuel;
		double req = Double.MAX_VALUE;
		
		long min = 1;
		long max = 1000000000L;
		for (int cur = 1 ; cur <= 10000 ; cur++) {
			long stp1 = (min * 2 + max) / 3;
			long stp2 = (min + max * 2) / 3;
			double d1 = 1.0d * distance / stp1;
			double d2 = 1.0d * distance / stp2;
			double fuel1 = tf * stp1 + ff(d1) * stp1;
			double fuel2 = tf * stp2 + ff(d2) * stp2;
			if (fuel1 > fuel2) {
				min = stp1;
			} else {
				max = stp2;
			}
		}
		
		for (long stp = min - 1000000 ; stp <= min + 1000000 ; stp++) {
			if (stp <= 0) {
				continue;
			}
			double d = 1.0d * distance / stp;
			double fuel1 = tf * stp + ff(d) * stp;
			req = Math.min(req, fuel1);
		}
		return req;
	}
}