#P1298. Closest Reduced Fraction

    ID: 14585 Type: Default 1000ms 256MiB

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