青少年信息学奥赛学习网

问题 1188. -- 最接近的分数

1188: 最接近的分数

时间限制: 1 Sec 内存限制: 128 MB
提交: 104 解决: 30
[提交][状态][讨论版]

给出一个正小数，找出分子与分母均不超过n的最简分数，使其最接近给出的小数。“最接近”是指在数轴上该分数距离给出的小数最近，如果这个分数不唯一，输出分子最小的一个。

输入共二行：
第一行只有一个正整数：n
第二行只有一个正实数：x

输出共二行：
第一行只有一个正整数：分子
第二行只有一个正整数：分母

5
0.51

1
2

样例#2输入：

10

0.24

样例#2输出：

1

4

【数据规模】 50% 的数据: 1 <= n <= 1 000。 80% 的数据: 1 <= n <= 100 000。 100% 的数据: 1 <= n <= 10 000 000