e-olymp 1610. Зайцы в клетках

Зайцы в клетках

Всем известен, так называемый, принцип Дирихле, который формулируется следующим образом:

Предположим, что некоторое число кроликов рассажены в клетках. Если число кроликов больше, чем число клеток, то хотя бы в одной из клеток будет больше одного кролика.

В данной задаче мы рассмотрим более общий случай этого классического математического факта. Пусть имеется клеток и зайцев, которых рассадили по этим клеткам. Вам требуется расcчитать максимальное количество зайцев, которое гарантированно окажется в одной клетке.

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

В одной строке заданы два натуральных числа $n$ и $m$ $(1 ≤ n, m ≤ 10^{9})$.

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

Максимальное количество зайцев, которое гарантированно окажется в одной клетке.

Тесты

ВХОДНЫЕ ДАННЫЕ ВЫХОДНЫЕ ДАННЫЕ
3 50 17
5 5 1
1070 589 1
20 150 8

Код программы

Решение задачи

Пусть $n$ — количество клеток, и $m$ — количество зайцев.
Найдем отношение $\frac{m}{n}$. Если это отношение больше либо равно единице то $m\geq n$ и мы имеем ответ. $\frac{m+n-1}{n}$ — это формула выводит ответ в целом виде, если он целый, и округляет в большую сторону, если он дробный. Иначе $m\leq n$ и максимальное гарантированное количество зайцев в одной клетке равно единице. Это следует из условия задачи.

Условие задачи на e-olimp
Код решения на ideon

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *