Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-01-10SRM483(DIV1)

SRM483 第一問(250pt) BestApproximationDiv1

|  SRM483 第一問(250pt) BestApproximationDiv1 - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM483 第一問(250pt) BestApproximationDiv1 - hama_DU@TopCoderへの道

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

1000(a) * 1000(b) で全探索余裕でした

何か引っ掛けがあるかと思いきや、特になし。

public class BestApproximationDiv1 {
	public int eq(double x, String number) {
		String enumber = String.valueOf(x);
		int size = enumber.length();
		if (size < 8) {
			for (int i = size ; i < 8 ; i++) {
				enumber += "0";
			}
		}
		int match = 0;
		for (int i = 0 ; i < 8 ; i++) {
			if (i == 1) continue;
			if (enumber.charAt(i) != number.charAt(i)) {
				break;
			}
			match++;
		}
		return match;
	}

	public String findFraction(int maxDen, String number) {
		int maxeq = 0;
		int maxa = 0;
		int maxb = 0;
		for (int a = 0 ; a <= maxDen ; a++) {
			for (int b = 0 ; b < a ; b++) {
				double d = b * 1.0 / a;
				int eq = eq(d, number);
				if (eq > maxeq) {
					maxeq = eq;
					maxa = a;
					maxb = b;
				}
			}
		}
		return maxb+"/"+maxa+" has "+maxeq+" exact digits";
	}
}