Война с ИИ: завоевать и угрожать
Задача по программированию с проверкой онлайн
- Сложность
- Сложная
- Языки
- Python
- JavaScript
- TypeScript
- Java
- Go
- Темы
- Деревья и графы
- Динамическое программирование
Вы воюете с искусственным интеллектом. Планеты пронумерованы от 0 до planets − 1; список wormholes состоит из пар [x, y] (x < y, пары не повторяются), каждая пара — двусторонняя червоточина между планетами. Ваша родная планета — 0, родная планета ИИ — 1, и от 0 до 1 всегда можно добраться по червоточинам.
Сначала вы владеете только планетой 0. Вы угрожаете планете, если не владеете ею и она соединена червоточиной хотя бы с одной вашей планетой. За ход можно завоевать любую планету, которой вы угрожаете, — она становится вашей. Как только вы начали угрожать планете 1, завоевания прекращаются.
Добейтесь угрозы планете 1, завоевав как можно меньше планет, а среди всех таких способов выберите тот, при котором в конце вы угрожаете наибольшему числу планет. Верните список [c, t]: c — число завоёванных планет, t — число планет под угрозой в конце (планета 1 тоже считается). Если 0 напрямую соединена с 1, ответ — [0, число соседей планеты 0]. Планет до 400, червоточин до 2000.
Пример: 7, [[0,6],[0,2],[0,4],[2,4],[3,4],[2,3],[3,5],[4,5],[1,5]] → [2, 4] (завоёвываем 4 и 5, угрожаем 6, 2, 3 и 1).
Источник: Coding Competitions Archive, codejam/2011/round_2/ai_war · © Google LLC · Apache-2.0 · условие переведено и дополнено