На сайте acmp.ru добавились 300 новых задач, и сейчас самое время их решить.
Вторая задача с регионального этапа Всероссийской олимпиады школьников по информатике 2010 года. Будем решать её с помощью бинпоиска по ответу.
Бинпоиск (метод деления отрезка пополам, дихотомия) - это алгоритм, с помощью которого можно находить корни монотонной функции на заданном отрезке. Заключается в том, что отрезок делится на две равные части и определяется, в какой из них находится искомый корень (а он может находиться только в одной из них, так как функция монотонна).
Данную задачу можно переформулировать таким образом: найти минимальный корень функции от одного параметра - размера доски (A), которая принимает два значения - 1, если доска для дипломов маленькая и не вмещает всех дипломов; 0, если доска подходящего размера. Очевидно, что такая функция монотонна.
Реализация этой функции очень простая. Будем размещать дипломы плотно к левому верхнему углу. Тогда количество рядов из дипломов будет равно C/h, а количество столбцов - C/w. Осталось определить отрезок, на котором искать ответ. Нижняя граница может быть 0, а верхняя - max(w, h) * n - когда все дипломы располагаются в один ряд/столбец. Здесь можно сделать и аккуратнее, но в этой задаче переполнение типа не грозит, поэтому экономим время для решения других задач.
Для разнообразия представляю решение на С++, но асимптотика бинпоска равна O(log len), где len - это длина отрезка, поэтому даже решение на Python справится моментально.
Обратите внимание на строку 17, что там присваивается c + 1, это сделано потому что в этом решении целочисленный бинпоиск, который может зациклиться из-за целочисленного деления в строке 13.
UPD: Как правильно заметили в комментарии, переполнение, всё-таки, грозит. И изначально в задаче были слабые тесты, которые пропускали моё решение, но потом были добавлены ещё тесты. Прикладываю корректное решение, в котором подбор диапазона для бинпоиска более точный:
Предыдущий выпуск: Задача 711. Соревнование картингистов
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.