Колода из улучшенных карт
Задача по программированию с проверкой онлайн
- Сложность
- Сложная
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Поиск и сортировка
- Массивы и списки
У игрока N карт и coins монет. Карта i может иметь уровень от 1 до K_i = len(powers[i]); на уровне j её сила равна powers[i][j-1] (сила строго растёт с уровнем). Сейчас карта на уровне levels[i]. Повысить карту i с уровня j до j + 1 стоит costs[i][j-1] монет; повышать можно только на один уровень за раз, но сколько угодно раз, пока хватает монет. Понижать уровни нельзя.
Игрок тратит часть монет (или ни одной) на повышения, а затем собирает колоду ровно из deck разных карт. Верните наибольшую возможную суммарную силу колоды. Монеты на карты вне колоды тратить бессмысленно, но разрешено.
Ограничения: 1 ≤ deck ≤ N ≤ 12, 1 ≤ K_i ≤ 5, 0 ≤ coins ≤ 3·10^9, силы и цены от 1 до 10^9; суммы не помещаются в 32 бита. В оригинальной игре deck = 8.
Пример: 10, 1, [1, 1], [[1, 50, 60], [30, 40]], [[6, 5], [3]] → 50 (первая карта до уровня 2 за 6 монет).
Источник: Coding Competitions Archive, kickstart/2016/round_a/clash_royale · © Google LLC · Apache-2.0 · условие переведено и дополнено