e-olymp 4050. Забавная игра

Ссылка на задачу.

Засчитанное решение.

В одной стране есть несколько аэропортов, между некоторыми аэропортами есть рейсы. Можно перелететь из любого аэропорта в любой другой, возможно, с несколькими пересадками. Для каждой пары аэропортов существует только одна последовательность рейсов, соединяющая эти аэропорты.

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

Напишите программу, которая по начальному списку полётов и номеру аэропорта, в котором террористы начинают игру, определяет, кто выигрывает, если террористы играют идеально (каждый выбирает лучший ход).

Входные данные

Первая строка содержит два целых числа: n и k, разделённые пробелом. Здесь n — количество аэропортов (n1000), а k — номер аэропорта, являющегося начальной точкой игры (1kn). Следующая n−1 строка содержит пары целых чисел, разделённых пробелами. Это номера аэропортов, соединённых рейсом. Все рейсы двусторонние и упомянуты только один раз. Каждый аэропорт соединён рейсами не более, чем с 20 другими.

Выходные данные

Если игрок, начинающий игру, выигрывает, программа должна написать «First player wins flying to airport L«, где L— номер аэропорта, в который игрок должен вылететь из текущего. Если таких аэропортов несколько, программа должна выбрать вариант с меньшим номером аэропорта. Если начинающий игрок проигрывает, программа должна написать «First player loses«.

Определяем массив аэропортов, булев массив пройденных аэропортов уровень вложенности функции dfs(), переменную запоминающую вторую вершину, булевы переменные для определения победителя, отсортированных вершин. В функции мы отмечаем первую вершину как пройденную переходим на следующий уровень. Сортируем все возможные варианты перехода, выбираем наименьший подходящий нам. Далее определяем переменную, которая считает вершины, в которые можно пойти из данной. В цикле проходим все вершины, пока проходим считаем количество детей.
Если оно равно нулю то это тупик.
И мы посмотрим кто бы выиграл если бы бандиты дошли до этого аэропорта.Если level нечетный, то мы ищем правильный ход первого, иначе второго террориста. Если уровень равен 1, то мы уже выходим. Выводим ответ. Иначе, если level не равен 1, то мы еще не дошли до конца и возвращаем выше, кто выигрывает в данном узле.
При этом каждый бандит ищет ветку где бы он победил.
Определяем количество детей. Если мы не в тупике, то но увеличивается на 1. Далее, если ходит второй террорист, то он выбирает ветку, в котором выиграет он. Если мы попали в тупик, выводим кто выиграл в зависимости от четности пройденного пути.
В main() считываем количество аэропортов и номер первого , записываем в вектора смежные аэропорты для каждого и запоминаем первую вершину. Запускаем dfs().

Зелінський Вячеслав Олександрович
Зелінський Вячеслав Олександрович

Latest posts by Зелінський Вячеслав Олександрович (see all)

One thought on “e-olymp 4050. Забавная игра

  1. Не очень хорошо получилось. Весьма сумбурное объяснение.
    — вместо коментариев при объявлении переменных Вы просто в объяснении перечисляете, что хранят переменные без указания их имени. Как понять какое объяснение относится к какой переменной?
    — много синтаксических ошибок, особенно в комментариях
    — оценка 4 из двадцати возможных (4 = 20 — 16)
    Жалко, что большая работа становится бесполезной для читателей из-за небрежного объяснения.

    P.S. Решение может быть вдвое лаконичнее.

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