Ровные куски блинов
Задача по программированию с проверкой онлайн
- Сложность
- Сложная
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Математика
- Словари и множества
- Поиск и сортировка
Даны куски блинов — круговые секторы с углами slices[i] (целые положительные числа) — и число гостей diners (от 2 до 50). Каждый гость должен получить ровно один кусок, и все розданные куски должны быть одного размера (какого — неважно, он не обязан быть целым). Один разрез делит кусок размера X на два куска размеров Y и X − Y для любого 0 < Y < X; получившиеся куски можно резать дальше. Лишние куски любых размеров можно оставить себе. Склеивать куски нельзя.
Верните наименьшее число разрезов, после которого можно накормить всех гостей. Кусков может быть до тысячи, углы — до 3.6·10^11.
Пример: [8, 4], 3 → 1 (кусок 8 режем пополам и раздаём три куска по 4).
Источник: Coding Competitions Archive, codejam/2020/round_1c/oversized_pancake_choppers · © Google LLC · Apache-2.0 · условие переведено и дополнено