Codeforces #172, Division 2, B : Nearest Fraction

問題文

http://codeforces.com/contest/281/problem/B

概要

分数 が与えられる。
分母が n を超えない既約分数のうち、 との差の絶対値が最も小さいものを求めよ。

解法

分母を決めると、分子とその分数の大きさは単調性を持ちます。
従って、分子を二分探索することができます。

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

int solve_bs( int x, int y, int b )
{
	double target = (double)x / y;

	int lb = 0, ub = 1000000;

	REP( t, 0, 100 )
	{
		int a = ( lb + ub ) / 2;

		if ( (double)a / b < target )
		{
			lb = a;
		}
		else
		{
			ub = a;
		}
	}

	int res;
	double diff = DBL_MAX;

	REP( a, lb - 10, ub + 10 )
	{
		double d = abs( (double)x / y - (double)a / b );

		if ( d < diff )
		{
			res = a;
			diff = d;
		}
	}

	return res;
}

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int x, y, n;
	cin >> x >> y >> n;

	int resa, resb;
	double diff = DBL_MAX;

	REP( b, 1, n + 1 )
	{
		int a = solve_bs( x, y, b );

		double d = abs( (double)x / y - (double)a / b );
		if ( d < diff )
		{
			resa = a;
			resb = b;
			diff = d;
		}
	}

	cout << resa << '/' << resb << endl;

	return 0;
}