Codeforces Round #172 (Div. 2) B. Nearest Fraction 二分

B. Nearest Fraction

Time Limit: 20 Sec

Memory Limit: 256 MB

题目连接

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

Description

You are given three positive integers x, y, n. Your task is to find the nearest fraction to fraction  whose denominator is no more than n.

Formally, you should find such pair of integers a, b (1 ≤ b ≤ n; 0 ≤ a) that the value  is as minimal as possible.

If there are multiple "nearest" fractions, choose the one with the minimum denominator. If there are multiple "nearest" fractions with the minimum denominator, choose the one with the minimum numerator.

Input

A single line contains three integers x, y, n (1 ≤ x, y, n ≤ 105).

Output

Print the required fraction in the format "a/b" (without quotes).

Sample Input

3 7 6

Sample Output

2/5

HINT

题意

给你a,b,n，让你找一个分数出来，使得其分母不大于n，并且这个分数最接近a/b的最简分数

题解：

直接暴力枚举分母，然后再二分分子就好了

然后更新答案

代码

#include<iostream>
#include<stdio.h>
#include<math.h>
using namespace std;

int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}
int main()
{
    int a,b,n;
    cin>>a>>b>>n;
    if(n>=b)
    {
        printf("%d/%d
",a/gcd(a,b),b/gcd(a,b));
        return 0;
    }
    double x = a*1.0 / b*1.0;
    int ans1 = 0,ans2 = 1;
    for(int i=1;i<=n;i++)
    {
        int l = 0,r = 100000;
        while(l<=r)
        {
            int mid = (l+r)/2;
            if(mid*1.0/(i*1.0)>=x)r=mid-1;
            else l=mid+1;
        }
        if(fabs((l-1)*1.0/(i*1.0)-x)<fabs((ans1*1.0)/(ans2*1.0)-x))
            ans1 = l-1,ans2 = i;
        if(fabs((l)*1.0/(i*1.0)-x)<fabs((ans1*1.0)/(ans2*1.0)-x))
            ans1 = l,ans2 = i;
    }
    printf("%d/%d
",ans1/gcd(ans1,ans2),ans2/gcd(ans1,ans2));
}