2012-07-10 11:07:49Morris
[UVA][eps] 906 - Rational Neighbor
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
*/