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 ...
  • ... and corresponding outputs

Copyright (c) IARCS 2003-2018;   Last Updated: 23 May, 2003