Hatena::Grouptopcoder

chokudaiの日記

 | 

2010-09-26

SRM 483 Div1 Easy BestApproximationDiv1

14:16 | SRM 483 Div1 Easy BestApproximationDiv1 - chokudaiの日記 を含むブックマーク はてなブックマーク - SRM 483 Div1 Easy BestApproximationDiv1 - chokudaiの日記 SRM 483 Div1 Easy BestApproximationDiv1 - chokudaiの日記 のブックマークコメント

問題

0 <= A < B <= maxDenで、string numberと一致する桁数がもっとも多いA/Bを出力せよ

同一の場合は、A,Bがもっとも小さいものを出力

回答

やるだけ

public class BestApproximationDiv1 {

    int besta, bestb;

    public string findFraction(int maxDen, string number)
    {
        long basenum = (long)(double.Parse(number) * 1000000 + 0.5);
        int a, b;
        int maxmatch = -1;
        int besta = 999, bestb = 999;
        for (a = 0; a <= maxDen; a++)
        {
            for (b = a + 1; b <= maxDen; b++)
            {
                long temp = (long)((a * 1000000.0 / b) + 1e-9);
                int match = getCollectDigits(basenum, temp);
                if (match > maxmatch)
                {
                    maxmatch = match;
                    besta = a;
                    bestb = b;
                }
            }
        }
        return String.Concat(besta, "/", bestb, " has ", maxmatch, " exact digits");
    }

    int getCollectDigits(long a, long b)
    {
        int i;
        int res = 0;
        int first = 1000000;
        for (i = 0; i < 7; i++)
        {
            if ((a / first) % 10 == (b / first) % 10) res++;
            else break;
            first /= 10;
        }
        return res;
    }
}
 |