Поглощение частиц
Задача по программированию с проверкой онлайн
- Сложность
- Средняя
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Массивы и списки
- Поиск и сортировка
Ваша частица имеет размер mote, вокруг есть другие частицы с размерами из списка others. Частица поглощает другую, только если та строго меньше её; после этого её размер увеличивается на размер поглощённой. Порядок поглощения вы выбираете сами. Перед игрой разрешены операции двух видов, в любом порядке и количестве: добавить частицу любого положительного целого размера или удалить любую из частиц списка. Верните наименьшее число операций, после которого ваша частица сможет поглотить все остальные. Список может быть пустым (ответ 0).
Пример: 10, [25, 20, 9, 100] → 2 (добавить частицу размера 3 и убрать частицу 100; размеры частиц могут выйти за пределы ограничений входных данных).
Источник: Coding Competitions Archive, codejam/2013/round_1b/osmos · © Google LLC · Apache-2.0 · условие переведено и дополнено