Indian National Olympiad in Informatics, 2003
Solution to Question 2, Nearest fraction
IARCS home > OLYMPIAD > Archives
The naive solution
For each input fraction a/b, we keep track of the largest
fraction below a/b and the smallest fraction above a/b that
we have seen so far. Initially, these values
are 1/99 and 98/99.
In a loop, we generate all possible fractions i/j. If the fraction
is proper, we check whether it lies above or below the
current input a/b. If it beats the current nearest fraction in
that direction, we update the value of the nearest fraction.
Notice that solution cycles through the entire set of fractions
for each input.
A smarter solution
We generate the entire set of proper fractions in the range
given and sort them in ascending order.
For each input fraction, we use binary search on the sorted
list to find the pair of fractions that are nearest to it.
Some general tips
The fractions should always be stored and compared in
terms of their integer numerators and denominators, rather
than being compared as floating point numbers, to avoid
errors due to loss of precsion.
A C program for the exhaustive solution to the problem
A C program for the solution using sorting and searching
Some test inputs ...
o Input 1
o Input 2
o Input 3
o Input 4
o Input 5
o Input 6
o Input 7
o Input 8
o Input 9
o Input 10
... and corresponding outputs
o Output 1
o Output 2
o Output 3
o Output 4
o Output 5
o Output 6
o Output 7
o Output 8
o Output 9
o Output 10
