## 原始题面

### Description

The FORTH programming language does not support floating-point arithmetic at all. Its author, Chuck Moore, maintains that floating-point calculations are too slow and most of the time can be emulated by integers with proper scaling. For example, to calculate the area of the circle with the radius $$R$$ he suggests to use formula like $$R \times R \times 355 / 113$$, which is in fact surprisingly accurate. The value of $$355 / 113 ≈ 3.141593$$ is approximating the value of $$\pi$$ with the absolute error of only about $$2\times10^{-7}$$. You are to find the best integer approximation of a given floating-point number $$A$$ within a given integer limit $$L$$. That is, to find such two integers $$N$$ and $$D$$ ($$1 \leqslant N, D \leqslant L$$) that the value of absolute error $$|A - N / D|$$ is minimal

### Input

The first line of input contains a floating-point number $$A$$ ($$0.1 \leqslant A < 10$$) with the precision of up to $$15$$ decimal digits. The second line contains the integer limit $$L$$. ($$1 \leqslant L \leqslant 100000$$)

### Output

Output file must contain two integers, N and D, separated by space

### Source

Northeastern Europe 2001, Far-Eastern Subregion

## 解题思路

min_diff 记录当前绝对值的最小值，ans_n, ans_d 分别为其对应的分子和分母

• 如果 N / D > A
• 如果 N / D - A < min_diff, 则更新 min_diff
• 否则 D 加一
• 如果 N / D < A
• 如果 A - N / D < min_diff, 则更新 min_diff
• 否则 N 加一
• N, D 有一个超出范围则结束

Show code