skynet | C++ для приматов

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 — это индексы двух узлов, между которыми мы хотим заблокировать переход. Если между ними нет связи, возникает ошибка. В конце строки обязательно должен стоить символ перехода на новую строку.

Программа:

#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;
            }
        }
        
    }
}

#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

Related Images:

Вторая по списку игра на сайте codingame.com проверяет умение примата пользоваться условными операторами, интуицией и программой по физике за десятый класс. По легенде, на постапокалиптических просторах Земли будущего раскинулась зловещая империя враждебных человеку роботов, но инженерный гений непокоренных программистов-взломщиков дает человечеству шанс на выживание. Подрывная деятельность начинается с малого: под дистанционный контроль удалось взять кремниевые мозги скоростного робота, внешностью и повадками напоминающего модифицированный мотоцикл. Наша задача — создать алгоритм управления, позволяющий машине преодолевать препятствия.

Инициализация:
Каждый уровень поделен на три этапа:

Движение по стартовой площадке.
Прыжок через пропасть.
Торможение на финишной прямой.

До начала игрового цикла программа считывает данные о длине каждого из элементов уровня и сохраняет соответственно в переменные [latex]R, G, L[/latex].

Игровой цикл
На каждой итерации входной поток содержит: