Problem B
Best Rational Approximation

Many microcontrollers have no floating point unit but do have a (reasonably) fast integer divide unit. In these cases it may pay to use rational values to approximate floating point constants. For instance,

\[ 355/113 = 3.1415929203539823008849557522124 \ldots \]

is a quite good approximation to

\[ \pi = 3.14159265358979323846 \ldots \]

A best rational approximation $p/q$ to a real number $x$ with denominator at most $M$ is a rational number $p/q$ (in lowest terms) with $q \le M$ such that, for any integers $a$ and $b$ with $b \le M$, and $a$ and $b$ relatively prime, $p/q$ is at least as close to $x$ as $a/b$:

\[ |x - p/q| \le |x - a/b| \]

Write a program to compute the best rational approximation to a real number, $x$, with denominator at most $M$.


The first line of input contains a single integer $P$, ($1 \le P \le 1\, 000$), which is the number of data sets that follow. Each data set should be processed identically and independently.

Each data set consists of a single line of input. It contains the data set number, $K$, followed by the maximum denominator value, $M$ ($15 \le M \le 1\, 000\, 000$), followed by a real number, $x$, ($0 \le x < 1$), given with at most $18$ digits after the period.


For each data set there is a single line of output. The single output line consists of the data set number, $K$, followed by a single space followed by the numerator, $p$, of the best rational approximation to $x$, followed by a forward slash (/) followed by the denominator, $q$, of the best rational approximation to $x$.

Sample Input 1 Sample Output 1
1 100000 0.141592653589793238
2 255 0.141592653589793238
3 15 0.141592653589793238
1 14093/99532
2 16/113
3 1/7
CPU Time limit 7 seconds
Memory limit 1024 MB
Statistics Show
Source 2017 Greater New York Region ACM Regional Contest
License For educational use only

Please log in to submit a solution to this problem

Log in