Hatena::Grouptopcoder

TopCoder戦記

研究開発者・ellerのTopCoder挑戦記録。言語は主にJavaを使用しています。ドキュメンテーションコメントはSubmit完了後、ブログ掲載前に補完したものです。

2010-09-26SRM483 DIV1

久々の本番参加。1問も正答できませんでしたが、challengeで+50ptとなったためかRatingは微増(1230→1261)となりました。

SRM483 DIV1 easy(250pt.)

| 09:06

残念ながら、本番ではyuyarin氏と同じ理由で落ちてしまいました。

やらしい... Test Case: 138 Args: {1000, "0.812983"} Expected: "313/385 has 6 exact digits" Received: "526/647 has 7 exact digits"less than a minute ago via YoruFukurou

修正したコードは以下。

import java.text.DecimalFormat;
import java.text.NumberFormat;

public class BestApproximationDiv1 {
	public String findFraction(int maxDen, String number) {
		NumberFormat format = new DecimalFormat("0.000000000");	// ゼロが足りずに落ちた
		int exact = 0, resultA = 0, resultB = 0;
		double numberF = Double.valueOf(number);

		for (int b = 1; b <= maxDen && exact != 7; ++b) {
			int firstA = Math.min(10 + (int)(b * numberF), b - 1);	// 枝刈り。10という数値には特に根拠なし
			for (int a = firstA; a >= 0; --a) {
				double f = a / (double) b;
				int same = sameOf(number, format.format(f));
				if (same > exact) {
					exact = same;
					resultA = a;
					resultB = b;
				} else if (same == exact && a < resultA) {
					resultA = a;
					resultB = b;
				}

				if (f < numberF) break;	// 枝刈り。
			}
		}
	
		return String.format("%d/%d has %d exact digits", resultA, resultB, exact);
	}

	private int sameOf(String number, String format) {
		for (int i = 0; i < number.length(); ++i) {
			if (number.charAt(i) != format.charAt(i)) return i - 1;
		}

		return 7;
	}

// BEGIN CUT HERE
	public static void main(String[] args) {
		BestApproximationDiv1 temp = new BestApproximationDiv1();
		System.out.println(temp.findFraction(1000, "0.000007"));
	}
// END CUT HERE
}