aprox

Fie $x$ un număr real subunitar cu cel mult $9$ zecimale și $N$ un număr natural.

Cerința

Să se determine fracția ireductibilă $\frac{a}{b}$ cu proprietățile:

• aproximează cel mai bine numărul real $x$, adică expresia $|x − \frac{a}{b}|$ are valoare minimă
• $1 \leq b \leq N$

Date de intrare

Fișierul de intrare aprox.in conține pe prima linie numărul real $x$, iar pe a doua linie numărul natural $N$, cu semnificaţia de mai sus.

Date de ieșire

Fișierul de ieșire aprox.out va conţine o singură linie pe care se vor scrie numerele naturale $a$ și $b$ reprezentând numărătorul și numitorul fracției ireductibile căutate, separate printr-un spațiu.

Restricții și precizări

• $0 < x < 1$
• $1 < N < 1 \ 000 \ 000 \ 000$
• Pentru teste în valoare de $14$ puncte: $1 \leq N \leq 500$
• Pentru alte teste în valoare de $31$ puncte: $1 \leq N \leq 1 \ 000 \ 000$
• Pentru alte teste în valoare de $55$ puncte: $1 \ 000 \ 001 \leq N \leq 1 \ 000 \ 000 \ 000$

Exemplul 1

aprox.in

0.318
100

aprox.out

7 22

Explicație

Fracția ireductibilă care aproximează cel mai bine numărul $0.318$ și are numitorul mai mic sau egal decât $100$ este $\frac{7}{22}$.

Exemplul 2

aprox.in

0.998977661
999999991

aprox.out

756463905 757238059

Explicație

Fracția ireductibilă care aproximează cel mai bine numărul $0.998977661$ și are numitorul mai mic sau egal decât $999999991$ este $\frac{756463905}{757238059}$.