/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 625 点
問題文
1 未満の正実数 r と正整数 N が与えられます。
0\leq p\leq q\leq N かつ \gcd(p,q)=1 を満たす整数の組 (p,q) のうち、\left\vert r-\dfrac pq\right\vert の値を最小にするものを求めてください。
ただし、そのような (p,q) が複数存在する場合、\dfrac pq の値が最も小さいものを出力してください。
制約
- 0\lt r\lt 1
- r は十進法で小数点以下たかだか 18 桁の実数として与えられる。
- 1\leq N\leq 10^{10}
- N は整数
入力
入力は以下の形式で標準入力から与えられる。
r N
出力
問題文の条件を満たす (p,q) について p と q をこの順に空白区切りで一行に出力せよ。
入力例 1
0.333 33
出力例 1
1 3
\left\vert0.333-\dfrac13\right\vert=\dfrac1{3000} です。
\left\vert0.333-\dfrac pq\right\vert\lt\dfrac1{3000} となる 0\leq p\leq q\leq33,\gcd(p,q)=1 は存在しないので、1 3 を出力してください。
入力例 2
0.45 5
出力例 2
2 5
\left\vert0.45-\dfrac12\right\vert=\left\vert0.45-\dfrac25\right\vert=\dfrac1{20} です。
\left\vert0.45-\dfrac pq\right\vert\lt\dfrac1{20} となる 0\leq p\leq q\leq5,\gcd(p,q)=1 は存在せず、\dfrac12\gt\dfrac25 が成り立つので、2 5 を出力してください。
入力例 3
0.314159265358979323 10000
出力例 3
71 226
\left\vert0.314159265358979323-\dfrac{71}{226}\right\vert=\dfrac{3014435336501}{113000000000000000000} です。
入力例 4
0.007735339533561113 7203576162
出力例 4
34928144 4515398949
Score : 625 points
Problem Statement
You are given a positive real number r less than 1, and a positive integer N.
Among the pair of integers (p,q) such that 0\leq p\leq q\leq N and \gcd(p,q)=1, find the one that minimizes \left\vert r-\dfrac pq\right\vert.
If multiple such pairs (p,q) exist, print the one with the smallest value of \dfrac pq.
Constraints
- 0\lt r\lt 1
- r is given as a real number with at most 18 decimal places.
- 1\leq N\leq 10^{10}
- N is an integer.
Input
The input is given from Standard Input in the following format:
r N
Output
For the pair (p,q) that satisfies the conditions in the problem statement, print p and q in this order, separated by a space, in a single line.
Sample Input 1
0.333 33
Sample Output 1
1 3
\left\vert0.333-\dfrac13\right\vert=\dfrac1{3000}.
There is no 0\leq p\leq q\leq33,\gcd(p,q)=1 such that \left\vert0.333-\dfrac pq\right\vert\lt\dfrac1{3000}, so print 1 3.
Sample Input 2
0.45 5
Sample Output 2
2 5
\left\vert0.45-\dfrac12\right\vert=\left\vert0.45-\dfrac25\right\vert=\dfrac1{20}.
There is no 0\leq p\leq q\leq5,\gcd(p,q)=1 such that \left\vert0.45-\dfrac pq\right\vert\lt\dfrac1{20}, and we have \dfrac12\gt\dfrac25, so print 2 5.
Sample Input 3
0.314159265358979323 10000
Sample Output 3
71 226
\left\vert0.314159265358979323-\dfrac{71}{226}\right\vert=\dfrac{3014435336501}{113000000000000000000}.
Sample Input 4
0.007735339533561113 7203576162
Sample Output 4
34928144 4515398949