Internet Problem Solving Contest

IPSC 2005

Problem E – Exact? Approximate!

Different people have different notions of entertainment. Some need the most incredible gadgets to play with, others are able to find pleasure in common everyday devices. This problem is dedicated to those, who have ever been amused by a pocket calculator (which is, unofficially, considered to be the 23rd most entertaining invention in the modern history of mankind).

One of the most popular calculator games has the following rules. Given a positive number X with D digits after the decimal point. Your task is to find a fraction A/B (where A and B are positive integers), that approximates the number X. More exactly, the value of A/B rounded to D digits after the decimal point must be exactly X. Moreover, we require that B is as small as possible. Note that the fraction A/B we seek is now unique.

Common rounding rules apply, i.e. 0-4 rounds down, 5-9 up. Thus:
1/3 rounded to 3 decimal places is 0.333
2/3 rounded to 3 decimal places is 0.667
5/10000 rounded to 3 decimal places is 0.001
5/10001 rounded to 3 decimal places is 0.000

Input specification

The input file consists of several lines. The i-th line contains one positive real number X_i in decimal notation. You can assume that X_i is less than one. Note that trailing zeroes are significant.

Output specification

For each line, output two positive integers A and B (separated by a single space character), such that the fraction A/B meets the requirements stated above.


1 3
2 5
2 3
7 10

Problemsetter(s): misof
Contest-related materials: Tono, misof, Meri
Special thanks: to Tomas Plachetka for bringing this problem into my attention ;)