Зайцы в клетках
Всем известен, так называемый, принцип Дирихле, который формулируется следующим образом:
Предположим, что некоторое число кроликов рассажены в клетках. Если число кроликов больше, чем число клеток, то хотя бы в одной из клеток будет больше одного кролика.
В данной задаче мы рассмотрим более общий случай этого классического математического факта. Пусть имеется [latex]n[/latex] клеток и [latex]m[/latex] зайцев, которых рассадили по этим клеткам. Вам требуется расcчитать максимальное количество зайцев, которое гарантированно окажется в одной клетке.
Входные данные
В одной строке заданы два натуральных числа [latex]n[/latex] и [latex]m[/latex] [latex](1 ≤ n, m ≤ 10^9)[/latex].
Выходные данные
Максимальное количество зайцев, которое гарантированно окажется в одной клетке.
Тесты
| Входные данные | Выходные данные |
|---|---|
| 3 50 | 17 |
| 5 5 | 1 |
| 1070 589 | 1 |
| 34 49 | 2 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 |
#include <iostream> using namespace std; int main() { int n, m; double k; cin >> n >> m; k = m / n; if (k >= 1)cout << (m + n - 1) / n; else cout << 1; return 0; } |
Решение задачи
Пусть [latex]n[/latex] — количество клеток, и [latex]m[/latex] — количество зайцев.
Найдем отношение [latex]\frac{m}{n}[/latex]. Если это отношение больше либо равно единице то [latex]{m}\geq{n}[/latex] и мы имеем ответ. [latex]\frac{(m+n-1)}{n}[/latex] — это формула выводит ответ в целом виде, если он целый, и округляет в большую сторону, если он дробный. Иначе [latex]{m}\leq{n}[/latex] и максимальное гарантированное количество зайцев в одной клетке равно единице. Это следует из условия задачи.
Условие задачи на e-olimp
Код решения ideon