Ctrl K

Срезать самую высокую кучу

Лёгкая
На столе лежат кучки монет, piles[i] — сколько монет в i-й кучке. Игра длится rounds раундов. В каждом раунде вы берёте самую высокую кучку (если таких несколько — любую из них) и забираете из неё монеты так, чтобы в ней осталось ⌊√x⌋, где x — сколько в ней было. Верните, сколько монет останется на столе во всех кучках вместе после всех раундов.
Пример 1
piles=[50, 10, 3], rounds=3 → 8

Сначала 50 → 7, затем самая высокая куча 10 → 3, затем 7 → 2. Остаётся 2 + 3 + 3 = 8.

Пример 2
piles=[100], rounds=5 → 1

100 → 10 → 3 → 1, а дальше куча из одной монеты уже не уменьшается.

Ограничения
  • 1 ≤ len(piles) ≤ 10⁵
  • 1 ≤ piles[i] ≤ 10⁹
  • 1 ≤ rounds ≤ 10⁵
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиРазобрать стопки поровну ЛёгкаяСнимать максимумы по строкам ЛёгкаяМаша и Петя раскладывают карты ЛёгкаяПодтянуть самого слабого ЛёгкаяХватит ли мест в шаттле Средняя
загружаем Python…
Вход
piles=[50, 10, 3], rounds=3
Ожидается
8

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 109 тестов на сервере, включая скрытые.