Зайцы в клетках
Всем известен, так называемый, принцип Дирихле, который формулируется следующим образом:
Предположим, что некоторое число кроликов рассажены в клетках. Если число кроликов больше, чем число клеток, то хотя бы в одной из клеток будет больше одного кролика.
В данной задаче мы рассмотрим более общий случай этого классического математического факта. Пусть имеется клеток и зайцев, которых рассадили по этим клеткам. Вам требуется расcчитать максимальное количество зайцев, которое гарантированно окажется в одной клетке.
Входные данные
В одной строке заданы два натуральных числа $n$ и $m$ $(1 ≤ n, m ≤ 10^{9})$.
Выходные данные
Максимальное количество зайцев, которое гарантированно окажется в одной клетке.
Тесты
| ВХОДНЫЕ ДАННЫЕ | ВЫХОДНЫЕ ДАННЫЕ |
| 3 50 | 17 |
| 5 5 | 1 |
| 1070 589 | 1 |
| 20 150 | 8 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
import java.util.*; import java.lang.*; import java.io.*; import java.util.Scanner; class Main { public static void main (String[] args) throws java.lang.Exception { int n, m; double k; Scanner in = new Scanner(System.in); n = in.nextInt(); m = in.nextInt(); k = m / n; if (k >= 1){ int k1 = (m + n - 1) / n; System.out.print(k1); } else System.out.print(1); } } |
Решение задачи
Пусть $n$ — количество клеток, и $m$ — количество зайцев.
Найдем отношение $\frac{m}{n}$. Если это отношение больше либо равно единице то $m\geq n$ и мы имеем ответ. $\frac{m+n-1}{n}$ — это формула выводит ответ в целом виде, если он целый, и округляет в большую сторону, если он дробный. Иначе $m\leq n$ и максимальное гарантированное количество зайцев в одной клетке равно единице. Это следует из условия задачи.