Билеты на плей-офф
Задача по программированию с проверкой онлайн
- Сложность
- Сложная
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Деревья и графы
- Динамическое программирование
В турнире на выбывание 2^P команд с номерами от 0 до 2^P − 1 (1 ≤ P ≤ 10) и P раундов. В первом раунде играют команды 0 и 1, 2 и 3 и так далее; в каждом следующем раунде победители соседних матчей предыдущего раунда встречаются в том же порядке, в последнем раунде один финал. Список prices из P списков: prices[r][j] — цена билета на j-й по порядку матч раунда r (с нуля), от 0 до 100000.
Болельщик готов пропустить не больше misses[i] матчей команды i (от 0 до P). Билеты покупаются заранее, до турнира, и набор билетов должен выполнять все эти условия при любых исходах матчей. Верните наименьшую суммарную цену такого набора.
Пример: misses = [1, 2, 3, 2, 1, 0, 1, 3], prices = [[100, 150, 50, 90], [500, 400], [800]] → 1350 (все возможные матчи команды 5 и первый матч команды 0).
Источник: Coding Competitions Archive, codejam/2010/round_2/world_cup_2010 · © Google LLC · Apache-2.0 · условие переведено и дополнено