Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-05-01SRM336,SRM337,SRM338 (Practice)

SRM 338 ImprovingStatistics

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

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

  • 二分探索するだけ
public class ImprovingStatistics {

	public int calcRate(long p, long w) {
		return (int)(w * 100 / p);
	}
	
	public long INF = 2000000000;
	
	public int howManyGames(int played, int won) {
		long pl = played;
		long wl = won;
		int rate = calcRate(pl, wl);
		int obj = rate + 1;
		
		if (calcRate(pl + INF, wl + INF) < obj) {
			return -1;
		}
		
		long max = INF;
		long min = 0;
		for (int c = 0 ; c < 100 ; c++) {
			long mid = (max + min) / 2;
			if (calcRate(pl + mid, wl + mid) >= obj) {
				max = mid;
			} else {
				min = mid;
			}
		}
		return (int)max;
	}
}