2013 TCO Round 1A Medium(500) TheFrog

TopCoder

TheFrog

Xは最小なので、少なくとも1個のR[i]を通る。kを整数として、X=R[i]/kとなる。またXが1未満になることはない。そのようなXを列挙してpitに落ちないかを調べる。

#include <vector>
using namespace std;

class TheFrog{public:
double getMinimum( int D, vector <int> L, vector <int> R )
{
    int n = (int)L.size();

    double ans = D;
    for ( int i=0; i<n; i++ )
    {
        for ( int k=1; k<=R[i]; k++ )
        {
            double X = (double)R[i]/k;
            bool f = true;
            for ( int j=0; j<n && f; j++ )
                if ( int(L[j]/X+1e-9)!=int(R[j]/X-1e-9) )
                    f = false;
            if ( f )
                ans = min( ans, X );
        }
    }
    return ans;
}};