Задача взята с сайта e-olymp
Задача
Всем известен, так называемый, принцип Дирихле, который формулируется следующим образом:
Предположим, что некоторое число кроликов рассажены в клетках. Если число кроликов больше, чем число клеток, то хотя бы в одной из клеток будет больше одного кролика.
В данной задаче мы рассмотрим более общий случай этого классического математического факта. Пусть имеется [latex]n[/latex] клеток и [latex]m[/latex] зайцев, которых рассадили по этим клеткам. Вам требуется расcчитать максимальное количество зайцев, которое гарантированно окажется в одной клетке.
Входные данные
В одной строке заданы два натуральных числа [latex]n[/latex] и [latex]m[/latex] (1 ≤ [latex]n[/latex], [latex]m[/latex] ≤ [latex]\ 10^{9}[/latex]).
Выходные данные
Максимальное количество зайцев, которое гарантированно окажется в одной клетке.
Тесты
| # | Входные данные | Выходные данные |
|---|---|---|
| 1 | 3 4 | 2 |
| 2 | 15 144 | 10 |
| 3 | 1 7 | 7 |
| 4 | 100 123456 | 1235 |
| 5 | 222 222 | 1 |
Код
|
1 2 3 4 5 6 7 8 9 10 11 |
#include < iostream > #include < cmath > using namespace std; int main() { long long n, m; cin >> n >> m; long long res = ceil(m / (double) n); cout << res; return 0; } |
Решение
Распределяя всех [latex] m [/latex] зайцев равномерно по клеткам [latex] n [/latex] получаем что максимальное количество зайцев в одной клетке равно [latex]\lceil \frac{m}{n}\rceil[/latex]