#1726

Внеземные цивилизации

Темы: [Алгоритмы на строках]

#1737

Заправки

Темы: [Алгоритм Флойда] [Алгоритм Дейкстры]

В стране \(N\) городов, некоторые из которых соединены между собой дорогами. Для того, чтобы проехать по одной дороге, требуется один бак бензина. В каждом городе бак бензина имеет разную стоимость. Вам требуется добраться из первого города в \(N\)-й, потратив как можно меньшее количество денег.

При этом есть ещё канистра для бензина, куда входит столько же бензина, сколько входит в бак. В каждом городе можно заправить бак, залить бензин в канистру, залить и туда и туда, или же перелить бензин из канистры в бак.

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

Во входном файле записано сначала число \(N\) (1 \(\le\) \(N\) \(\le\) 100), затем идёт \(N\) чисел, \(i\)-ое из которых задает стоимость бензина в \(i\)-ом городе (всё это целые числа из диапазона от 0 до 100). Затем идет число \(M\) — количество дорог в стране, далее идет описание самих дорог. Каждая дорога задается двумя числами — номерами городов, которые она соединяет. Все дороги двухсторонние (то есть по ним можно ездить как в одну, так и в другую сторону), между двумя городами всегда существует не более одной дороги, не существует дорог, ведущих из города в себя.

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

В выходной файл выведите одно число — суммарную стоимость маршрута или −1, если добраться невозможно.

Примеры

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

4
1 10 2 15
4
1 2 1 3 4 2 4 3

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

#1738

Сортировка вагонов

Темы: [Стек]

К тупику со стороны пути 1 (см. рисунок) подъехал поезд. Разрешается отцепить от поезда один или сразу несколько первых вагонов и завезти их в тупик (при желании, можно даже завезти в тупик сразу весь поезд). После этого часть из этих вагонов вывезти в сторону пути 2. После этого можно завезти в тупик еще несколько вагонов и снова часть оказавшихся вагонов вывезти в сторону пути 2. И так далее (так, что каждый вагон может лишь один раз заехать с пути 1 в тупик, а затем один раз выехать из тупика на путь 2). Заезжать в тупик с пути 2 или выезжать из тупика на путь 1 запрещается. Нельзя с пути 1 попасть на путь 2, не заезжая в тупик.

Известно, в каком порядке изначально идут вагоны поезда. Требуется с помощью указанных операций сделать так, чтобы вагоны поезда шли по порядку (сначала первый, потом второй и т.д., считая от головы поезда, едущего по пути 2 в сторону от тупика).

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

Вводится число \(N\) — количество вагонов в поезде (1≤N≤2000). Дальше идут номера вагонов в порядке от головы поезда, едущего по пути 1 в сторону тупика. Вагоны пронумерованы натуральными числами от 1 до \(N\), каждое из которых встречается ровно один раз.

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

Если сделать так, чтобы вагоны шли в порядке от 1 до N, считая от головы поезда, когда поезд поедет по пути 2 из тупика, можно, выведите действия, которые нужно проделать с поездом. Каждое действие описывается двумя числами: типом и количеством вагонов:

1) если нужно завезти с пути 1 в тупик K вагонов, должно быть выведено сначала число 1, а затем — число \(K\) (\(K\)≥1),

2) если нужно вывезти из тупика на путь 2 K вагонов, должно быть выведено сначала число 2, а затем — число \(K\) (\(K\)≥1).

Если возможно несколько последовательностей действий, приводящих к нужному результату, выведите любую из них.

Если выстроить вагоны по порядку невозможно, выведите одно число 0.

Примеры

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

3
3 2 1

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

YES

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

4
4 1 3 2

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

YES

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

3
2 3 1

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

NO

#1739

Игра с фишками

Темы: [Алгоритмы на графах]

Вы являетесь одним из разработчиков новой компьютерной игры. Игра происходит на прямоугольной доске, состоящей из \(W\) × \(H\) клеток. Каждая клетка может либо содержать, либо не содержать фишку (см. рисунок).

Важной частью игры является проверка того, соединены ли две фишки путем, удовлетворяющим следующим свойствам:

1) Путь должен состоять из отрезков вертикальных и горизонтальных прямых.

2) Путь не должен пересекать других фишек.

При этом часть пути может оказаться вне доски. Например:

Фишки с координатами (1,3) и (4,4) могут быть соединены. Фишки с координатами (2,3) и (5,3) тоже могут быть соединены. А вот фишки с координатами (2,3) и (3,4) соединить нельзя – любой соединяющий их путь пересекает другие фишки.

Вам необходимо написать программу, проверяющую, можно ли соединить две фишки путем, обладающим вышеуказанными свойствами, и, в случае положительного ответа, определяющую минимальную длину такого пути (считается, что путь имеет изломы, начало и конец только в центрах клеток (или «мнимых клеток», расположенных вне доски), а отрезок, соединяющий центры двух соседних клеток, имеет длину 1).

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

Первая строка входного файла содержит два натуральных числа: \(W\) – ширина доски, \(H\) – высота доски (1≤\(W\),\(H\)≤75). Следующие \(H\) строк содержат описание доски: каждая строка состоит ровно из W символов: символ «X» (заглавная английская буква «экс») обозначает фишку, символ «.» (точка) обозначает пустое место. Все остальные строки содержат описания запросов: каждый запрос состоит из четырёх натуральных чисел, разделённых пробелами – \(X_1\), \(Y_1\), \(X_2\), \(Y_2\), причём 1≤\(X_1\),\(X_2\)≤\(W\), 1≤\(Y_1\),\(Y_2\)≤\(H\). Здесь (\(X_1\), \(Y_1\)) и (\(X_2\), \(Y_2\)) – координаты фишек, которые требуется соединить (левая верхняя клетка имеет координаты (1,1)). Гарантируется, что эти координаты не будут совпадать (кроме последнего запроса; см. далее). Последняя строка содержит запрос, состоящий из четырёх чисел 0; этот запрос обрабатывать не надо. Количество запросов не превосходит 20.

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

Для каждого запроса необходимо вывести одно целое число на отдельной строке – длину кратчайшего пути, или 0, если такого пути не существует.

Примеры

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

5 4
XXXXX
X...X
XXX.X
.XXX.
2 3 5 3
1 3 4 4
2 3 3 4
0 0 0 0

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

5
6
0

#1741

Теннис

Темы: [Арифметические алгоритмы]

Источники: [ Личные олимпиады, Открытая олимпиада школьников, 2008-2009, Заочный этап, Задача A ]

В настольном теннисе в результате каждой подачи разыгрывается одно очко. Подача переходит от игрока к игроку каждые 5 подач, т.е. первые пять раз подает первый игрок, затем 5 раз — второй, затем снова первый и т.д.

Партия играется до тех пор, пока кто-нибудь из игроков не наберет 21 очко. Тот, кто набрал 21 очко, признается победителем, и игра заканчивается.

Вася и Петя играли в игру, и забыли, кто должен подавать в данный момент. Однако они помнят, что первую подачу делал Вася, и счет в настоящий момент a:b (a очков у Васи и b очков у Пети). Напишите программу, которая по данным a и b будет определять, чья подача или устанавливать, что игра закончена.

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

Вводятся два числа a и b. Числа соответствуют реальному счету, т.е. оба числа целые, от 0 до 21 и не равны 21 одновременно.

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

Выведите одно из четырех сообщений:

· Vasya serves — если сейчас должен подавать Вася

· Petya serves — если сейчас должен подавать Петя

· Vasya wins — если игра завершена и выиграл Вася

· Petya wins — если игра завершена и выиграл Петя

Примеры

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

4 1

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

Petya serves

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

15 0

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

Petya serves

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

21 12

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

Vasya wins