SRM483 Div1 Easy(250) BestApproximationDiv1

TopCoder

BestApproximationDiv1

A,Bの取り得る範囲を全部試しても間に合う。ただ誤差が怖い。本番の時はコメントアウトしているコードで通ったけど、例えば"%.10f"を"%.20f"とすると、

Problem: 250
Test Case: 10
Succeeded: No
Execution Time: 221 ms
Args:
{656, "0.120014"}

Expected:
"3/25 has 5 exact digits"

Received:
"49/408 has 5 exact digits"

でアウト。
VC++では問題無かったけど、GCCだと
printf("%.20f\n",(double)3/25); = "0.11999999999999999556"。
整数で処理するべき。

#include <string>

using namespace std;

class BestApproximationDiv1{public:
string findFraction( int maxDen, string number )
{
    int aA = 0;
    int aB = 0;
    int aX = -1;

    for ( int B=1; B<=maxDen; B++ )
    for ( int A=0; A<B; A++ )
    {
        /*
        char num[100];
        sprintf( num, "%.10f", (double)A/B );
        /*/
        char num[100] = "0.";
        sprintf( num+2, "%06d", A*1000000/B );
        //*/
        int X;
        for ( X=0; X<8; X++ )
            if ( num[X] != number[X] )
                break;

        if ( X > aX )
            aA = A,  aB = B,  aX = X;
    }

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