Problem B

Rational Neighbor

Introduction

As we know, finding a rational close to a given rational is straightforward. The minimal distance between two distinct integers is 1. By contrast, there is no minimal distance between two distinct rationals. A straightforward method for finding a rational close to a given rational a/b is based on the following construction. For every m > 0 one has a/b = (a m)/(b m), and the neighbors (a m ± 1)/(b m) lie at distance 1/(b m) from the given rational. So, by choosing m to be sufficiently large, one can make the distance to be as small as we please.

Problem

Given a rational a/b and an upper bound n for the distance, the problem consists to find the rational c/d such that:

(i)

a/b < c/d;

(ii)

the distance between the rationals a/b and c/d is smaller or equal than n;

(iii)

the denominator d is as small as possible.

Input

The input will contain several test cases, each of them consisting of two lines.
The first line of the input contains two positive integers a and b which define the rational number a/b. The integers a and b are assumed to be in the interval [1,100000]. The second line contain a positive real number n, 0.00000001≤ n ≤ 0.1, which gives the maximum distance allowed.

Output

For each test case, write to the output, on a line by itself, the two positive integers c and d which solve the problem.

Sample Input

96 145
0.0001

Sample Output

49 74

---

題目不難, 但是精準度很難調, 最後使用了 long double 才過


#include <stdio.h>

int main() {
    long long a, b, c, d;
    double eps;
    while(scanf("%lld %lld", &a, &b) == 2) {
        scanf("%lf", &eps);
        long double t1 = (long double)a/b, t2;
        for(d = 1; ; d++) {
            c = (long long)(t1*d);
            while(a*d >= b*c)
                c++;
            t2 = (long double)c/d;
            if(t2-t1 <= eps) {
                printf("%lld %lld\n", c, d);
                break;
            }
        }
    }
    return 0;
}
/*
89 144 0.00000001
*/