P17288 [HackerRank] Minimal distance to pi
提高-
题目描述

Given two long integers, $\text{min}$ and $\textit{max}$, find and print a common fraction, $\frac{n}{d}$, such that $min\leq d\leq max$ and $|\frac{n}{d}-\pi|$ is minimal (recall that $\pi\approx3.1415926535897932384626433832795028841971693993751$). If there are several fractions having minimal distance to $\textbf{\pi}$, choose the one with the smallest denominator.

Input Format

Two space-separated long integers describing the respective values of $\text{min}$ and $\textit{max}$.

Constraints

$1\le\textit{min}\le\textit{max}\le10^{15}$

Output Format

Print your answer in the form n/d, where $n$ is the numerator of the fraction closest to $\textbf{\pi}$ and $\boldsymbol{d}$ is the denominator of that fraction.

Sample Input 0
1 10

Sample Output 0
22/7

Explanation 0

We must check all fractions with denominators from $\textit{min}=1$ to $max=10$:

For $\boldsymbol{d}=1$: $\frac{3}{1}\leq\pi\leq\frac{4}{1}$, the closest fraction is $\frac{3}{1}$ and the distance is $\left|\frac{3}{1}-\pi\right|\approx0.142$.
For $\boldsymbol{d}=2$: $\frac{6}{2}\leq\pi\leq\frac{7}{2}$, the closest fraction is $\frac{6}{2}$ and the distance is $\left|\frac{6}{2}-\pi\right|\approx0.142$.
For $\boldsymbol{d}=3$: $\frac{9}{3}\leq\pi\leq\frac{10}{3}$, the closest fraction is $\frac{9}{3}$ and the distance is $\left|\frac{9}{3}-\pi\right|\approx0.142$.
For $\boldsymbol{d}=4$: $\frac{12}{4}\leq\pi\leq\frac{13}{4}$, the closest fraction is $\frac{13}{4}$ and the distance is $\left|\frac{13}{4}-\pi\right|\approx0.108$.
For $\boldsymbol{d}=5$: $\frac{15}{5}\leq\pi\leq\frac{16}{5}$, the closest fraction is $\frac{16}{5}$ and the distance is $\left|\frac{16}{5}-\pi\right|\approx0.058$.
For $\boldsymbol{d=6}$: $\frac{18}{6}\leq\pi\leq\frac{19}{6}$, the closest fraction is $\frac{19}{6}$ and the distance is $\left|\frac{19}{6}-\pi\right|\approx0.025$.
For $\boldsymbol{d}=7$: $\frac{21}{7}\leq\pi\leq\frac{22}{7}$, the closest fraction is $\frac{22}{7}$ and the distance is $\left|\frac{22}{7}-\pi\right|\approx0.001$.
For $\boldsymbol{d}=8$: $\frac{25}{8}\leq\pi\leq\frac{26}{8}$, the closest fraction is $\frac{25}{8}$ and the distance is $\left|\frac{25}{8}-\pi\right|\approx0.017$.
For $\boldsymbol{d}=9$: $\frac{28}{9}\leq\pi\leq\frac{29}{9}$, the closest fraction is $\frac{28}{9}$ and the distance is $\left|\frac{28}{9}-\pi\right|\approx0.030$.
For $\boldsymbol{d}=10$: $\frac{31}{10}\leq\pi\leq\frac{32}{10}$, the closest fraction is $\frac{31}{10}$ and the distance is $\left|\frac{31}{10}-\pi\right|\approx0.042$.

Of these, the closest approximation is $\frac{22}{7}$ with a distance to $\textbf{\pi}$ of about $\boldsymbol{0.001}$, so we print 22/7 as our answer.

输入格式

见题面

输出格式

见题面

样例输入
1 10
样例输出
22/7