SRM483 Div2 Hard(1000) BestApproximationDiv2

○○Div1と○○Div2があったらDiv2の方が簡単かと思いきや、今回はDiv2の方が難しい。numberの長さがintで扱いきれないので自前で割り算を実装。O(maxDen²)では間に合わないので、Bの値からAの値を計算。

#include <string>

using namespace std;

int quality( string number, int A, int B )
{
    int n = (int)number.length() - 2;

    for ( int i=0; i<n; i++ )
    {
        A *= 10;
        if ( number[i+2] != '0' + A / B )
            return i + 1;
        A -= A / B * B;
    }

    return n+1;
}

class BestApproximationDiv2{public:
string findFraction( int maxDen, string number )
{
    double num;
    sscanf( number.c_str(), "%lf", &num );

    int aA = 0,  aB = 0,  aX = 0;

    for ( int B=1; B<=maxDen; B++ )
    {
        int t = int( B * num );

        for ( int A=max(t-1,0); A<=min(t+1,B-1); A++ )
        {
            int X = quality( number, A, B );
            if ( X > aX )
                aA = A,  aB = B,  aX = X;
        }
    }

    char ans[100];
    sprintf( ans, "%d/%d has %d exact digits", aA, aB, aX );
    return ans;
}};