#P1298. Closest Reduced Fraction
Closest Reduced Fraction
Closest Reduced Fraction
Given a positive decimal number, and two positive integers M and N, find the simplest fraction (or integer) with numerator not exceeding M (with numerator \( \ge 0 \)) and denominator not exceeding N which is closest to the given decimal number. A fraction is in simplest form if it cannot be further reduced (i.e. the numerator and denominator are coprime, except for 0 which is represented as 0). "Closest" means that on the number line, the absolute difference between the fraction and the given decimal is minimized. If there exist two or more distinct fractions achieving the same minimum distance, output TOO MANY
instead.
Note: The fraction representing an integer should be output as the integer itself (e.g. 3 instead of 3/1), and 0 should be output as 0.
Formula formatting: Use \(a/b\) for fractions.
inputFormat
The input consists of a single line containing a positive decimal number d followed by two integers M and N separated by spaces.
Constraints:
- \(d\) is a positive decimal.
- 0 \(\leq M\)
- \(N \geq 1\)
outputFormat
Output the simplest fraction (or integer) that is closest to d. If there exist two or more distinct fractions with the same minimal distance, output TOO MANY
.
sample
0.33 5 7
1/3