Best Approximation
TopCoder SRM 483
Time Limit: 0.5s, Memory Limit: 64MiB
Ели не е голям фен на математическите константи. Повечето от тях са безкрайни, демек сложни за запомняне. Дробите, от друга страна, са значително по-лесни в това отношение, а понякога предоставят добро приближение на константите. Например, 22/7 = 3.1428… е един лесен начин да запомним как започва числото . Някои дроби дават значително по-добро приближение от други. Например 355/113 = 3.14159292… е точно до 7-мата цифра, вместо до 3-тата, както беше в случая с 22/7.

Вие искате да помогнете на Ели като намерите дробта, която най-добре апроксимира някакво дадено число N. Разбира се, тъй като ако самата дроб е много голяма, тя отново ще е сложна за запомняне, Ели ви е казала и едно число M - колко най-голям може да бъде нейният знаменател.
Вход
На първия ред на стандартния вход ще бъде зададено едно цяло число M – максималният знаменател, който може да има намерената дроб. На втория ред ще бъде зададено числото N, което трябва да апроксимирате. Числото ще е зададено с не повече от 49 цифри (тоест общо 50 знака с десетичната точка).
Изход
На стандартния изход изведете "A/B has X exact digits", където A/B е желаната дроб, а X е броят цифри преди първата разлика (без да прилагате каквото и да е закръгляне) с даденото число. Дробта, която извеждате, трябва да максимизира X. В случай, че съществува повече от едно възможно решение, изведете това с минимален знаменател. Ако все още има повече от един вариант, изведете това с минимален числител.
Ограничения
  • 0 < N < 10
  • 1 ≤ M ≤ 1,000,000
Примерен Вход Примерен Изход
42 3.141592658 22/7 has 3 exact digits
1000 2.718281828459045 1457/536 has 6 exact digits
3 0.1337 0/1 has 1 exact digits
80000 0.1234567891011121314151617181920 10/81 has 8 exact digits
100 0.42 3/7 has 3 exact digits
100 0.420 21/50 has 4 exact digits
1000000 5.319017212244471 355688/66871 has 15 exact digits
Забележете, че числителят на намерената дроб може да бъде по-голям от M. Също така забележете, че нули на края на числото биват броени към броя правилно апроксимирани цифри.
Мрън!