SRM 483 div1 easy: BestApproximationDiv1

問題

TopCoder Statistics - Problem Statement

解法

maxDen の値が小さいので, A, B のすべての候補を総当りします。

B/A の小数点以下の数は, B/A をそのまま見ると整数部分, 10*B/A を見ると小数点第一位以上, 100*B/A を見ると小数点第二位以上が見れる, などというのを利用しました。

class BestApproximationDiv1 {
public:
    string findFraction(int maxDen, string number) {
        string s;
        for (char c : number) {
            if (c != '.') s += c;
        }
        int bestA = -1, bestB = -1, best = 0;
        for (int B = 1; B <= maxDen; B++) for (int A = 0; A < B; A++) {
            string t;
            int b = B, a = A;
            for (int i = 0; i < 7; i++) {
                t += (char)('0'+(a/b));
                a -= (a/b)*b;
                a *= 10;
            }
            int score = 0;
            for (; score < 7; score++) {
                if (t[score] != s[score]) break;
            }
            if (score > best) {
                bestA = A;
                bestB = B;
                best = score;
            }
        }
        stringstream ss;
        ss << bestA << "/" << bestB << " has " << best << " exact digits";
        return ss.str();
    }
};