Skynet: the Virus

Skynet


SKYNET FINALE — LEVEL 1


Вирус

Los Angeles 2029 — Resistance HQ — Review of facts:

В минувшую субботу, сотни отважных бойцов рисковали своей жизнью, чтобы уничтожить Skynet. СТОП

Используя зараженных мото-терминаторов, им удалось привить смертельный вирус к Skynet. СТОП

Проблема: Skynet борется. СТОП

Джон, ещё раз,  нам нужна ваша помощь. СТОП


Задача:

У нас в распоряжении целый граф узлов. Некоторые из них названы шлюзами. Шлюзы надо защищать от злобного Skynet агента, который способен передвигаться по связям между узлами. Способ защиты очень прост: каждый ход можно навсегда заблокировать одну связь, тем самым, через некоторое количество ходов, полностью закрыть шлюз от нежелательных гостей.

Первичная инициализация:

Первая строка: 3 целых числа N L E

  • N — Количество узлов, включая шлюзы
  • L — Количество связей
  • E — Количество шлюзов

Следующие L строк: по два числа на строку (N1, N2), означающие, что между узлами с индексами N1 и N2 присутствует связь.
Следующие E строк: по одному числу на строку, означающие индексы шлюзов.

Инициализация за каждый игровой тик:

Одно число — индекс связи, на которой находится Skynet агент.

Вывод за каждый игровой тик:

Одна строка в которой присутствует два числа C1 и C2. C1 и C2 — это индексы двух узлов, между которыми мы хотим заблокировать переход. Если между ними нет связи, возникает ошибка. В конце строки обязательно должен стоить символ перехода на новую строку.

Программа:

Идея решения: Всё предельно просто: Если агент находится вблизи одного из шлюзов, закрываем переход между агентом и этим шлюзом. Иначе закрываем переход между шлюзом и ближайшим узлом.

Переходы между узлами занесены в двумерный массив N1, далее этот массив был своеобразно отсортирован (для удобства). В игровом цикле объявляем булевую переменную AgentIsNear — агент вблизи шлюза.

Первый цикл: Проверяем каждую клетку вокруг каждого шлюза на присутствие там агента. И если он таки там есть, блокируем переход, меняем первую переменную (отвечающую за шлюз) в массиве переходов (N1) на -1 (значение, которое никогда не встретится), изменяем AgentIsNear на true и прерываем цикл.

Второй цикл: так как агент гуляет где-то далеко, то мы блокируем любой свободный проход любого шлюза.

Второй цикл выполняется только тогда, когда за весь первый цикл условие внутри него ни разу не стало истинным.

Программа проходит все тесты на MEDIUM и, что удивительно, половину тестов на HARD! Взято с CodinGame

 

4 thoughts on “Skynet: the Virus

Добавить комментарий