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 — это индексы двух узлов, между которыми мы хотим заблокировать переход. Если между ними нет связи, возникает ошибка. В конце строки обязательно должен стоить символ перехода на новую строку.
Программа:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; int main() { int N; //Количество узлов, включая шлюзы int L; //Количество связей int E; //Количество шлюзов cin >> N >> L >> E; cin.ignore(); int N1[L][2]; // Массив для связей for (int i = 0; i < L; i++) { cin >> N1[i][0] >> N1[i][1]; cin.ignore(); } int EI[E]; // Индексы шлюзов for (int i = 0; i < E; i++) { cin >> EI[i]; cin.ignore(); } // Алгоритм сортировки (его достаточно) for(int i = 0; i < L; i++){ for(int k =0; k < E; k++){ if(N1[i][1] == EI[k]) swap(N1[i][1],N1[i][0]); } } // игровой цикл while (1) { int SI; //Индекс связи, на которой находится Агент cin >> SI; cin.ignore(); bool AgentIsNear = false; //Агент возле шлюза! for(int i = 0; i < L; i++){ bool T = false; //Для прерывания цикла for(int k = 0; k < E; k++){ if(EI[k] == N1[i][0] && SI == N1[i][1]){ cout << EI[k] << ' ' << SI << endl; N1[i][0] = -1; AgentIsNear = true; T = true; break; } } if(T) break; } if(!AgentIsNear){ for(int i = 0; i < L; i++){ bool T = false; //Для прерывания цикла for(int k = 0; k < E; k++){ if(N1[i][0] == EI[k]){ cout << EI[k] << ' ' << N1[i][1] << endl; N1[i][0] = -1; T = true; break; } } if(T) break; } } } } |
Переходы между узлами занесены в двумерный массив N1, далее этот массив был своеобразно отсортирован (для удобства). В игровом цикле объявляем булевую переменную AgentIsNear — агент вблизи шлюза.
Первый цикл: Проверяем каждую клетку вокруг каждого шлюза на присутствие там агента. И если он таки там есть, блокируем переход, меняем первую переменную (отвечающую за шлюз) в массиве переходов (N1) на -1 (значение, которое никогда не встретится), изменяем AgentIsNear на true и прерываем цикл.
Второй цикл: так как агент гуляет где-то далеко, то мы блокируем любой свободный проход любого шлюза.
Второй цикл выполняется только тогда, когда за весь первый цикл условие внутри него ни разу не стало истинным.
Программа проходит все тесты на MEDIUM и, что удивительно, половину тестов на HARD! Взято с CodinGame
Молодец. ЗасчитаНО:
— Роман, сделайте, пожалуйста ссылку на сайт с игрой.
— Вы не написали, программа проходит все тесты?
— «сотни отважный» — поправьте, пожалуйста.
Исправлено
Указано ли где-нибудь условие о том, что две вершины соединены не более чем одним ребром?
В условии вроде не уточняется.