Длинный Питон. Нужна формула [закрыт]

142

20 сентября 2019, 23:20

После того, как Мартышка и Попугай досконально исследовали длину Удава, им стало очень скучно. Тут Слонёнок вспомнил, что в лесу живет ещё Питон, которого тоже можно измерять! Друзья сразу же отправились на его поиски.

Питон, как и Удав, тоже целый, поэтому его нельзя мерить половинками. Измерив Питона, Мартышка и Попугай узнали, что в Питоне помещается n целых Попугаев или m целых Мартышек. Обрадованная Мартышка убежала сообщить полученный результат Слонёнку. Когда она ушла, Попугая заинтересовал следующий вопрос: а сколько раз он помещается в одной Мартышке?

Так как Мартышка убежала, и измерить её он не может, Попугай решил попытаться выяснить, сколько целых Попугаев может поместиться в одной Мартышке, используя результаты измерения Питона. По заданным n и m выясните, какое минимальное и максимальное число целых Попугаев может помещаться в одной Мартышке.

Входные данные

Во входном файле заданы два целых числа n и m, каждое на своей строке — количество Попугаев и Мартышек в Питоне, соответственно (1 ≤ n, m ≤ 10^9).

Выходные данные

В выходной файл выведите два числа — минимальное и максимальное количество целых Попугае в одной Мартышке.

Answer 1

Пусть питон имеет длину x, попугай — y, мартышка — z.

Пока не обращаем внимание на целочисленность операций, записываем из условия:

n = x / y
m = x / z

отсюда не сложно выразить:

r = z / y = n / m

Теперь вспоминаем, что деление у нас целочисленное и фактическая длина питона в попугаях лежит в интервале [n; n+1), а в мартышках — в интервале [m; m+1).

Таким образом, пользуясь свойствами обыкновенных дробей, устанавливаем, что наименьшее возможное количество попугаев в мартышке (строго) больше n / (m+1), а наименьшее возможное — (строго) меньше (n+1) / m.

Ваша задача сводится к отысканию этих двух чисел.

Например, если на входе у нас n = 10 и m = 3, то 10 / 4 = 2.5 < r < 11 / 3 = 3.667, т. е. результат 2 3 (2 всё же может быть: r=2.6 > 2.5, но в целых это r=2).

Или, если n = 499 и m = 5, то 499 / 6 = 83.167 < r < 500 / 5 = 100, т. е. результат 83 99 (100, понятно, быть не может).

Таким образом, окончательно: Floor(n/(m+1)) <= r < Ceiling((n+1)/m) или Floor(n/(m+1)) <= r <= Ceiling((n+1)/m)-1, вот эти две границы и пишите в ответ.

Здесь Floor — округление в вниз, а Ceiling — округление вверх.