Круг разделён на шесть секторов, в каждом из которых стоит фишка. Разрешается за один ход сдвинуть любые две фишки в соседние с ними сектора.
Можно ли с помощью таких операций собрать все фишки в одном секторе?

   Решение

Игровое поле представляет собой N кружков, некоторые из которых соединены отрезками. Каждому кружку приписана какая-то стоимость, а на каждом отрезке поставлена стрелка. Один из кружков является начальным, другой – конечным. Игрок должен переместить фишку из начального кружка в конечный, пройдя по каждому из отрезков ровно один раз. За перемещение по отрезку он получает определенное количество очков, равное стоимости кружка, в который он перемещается, взятой со знаком плюс, если движение происходит по направлению стрелки, и со знаком минус – если в противоположном. 

Требуется определить максимальное количество очков, которое может набрать игрок в этой игре.

Входные данные
Входной файл содержит исходные данные в следующей последовательности: N, x₁, x₂, ..., x_N, b, q, M, u₁, v₁, u₂, v₂, ..., u_M, v_M. Здесь N – количество кружков (1 ≤ N ≤ 30), x_i – стоимость, приписанная i-му кружку (1 ≤ x_i ≤ 30 000), b и q – номера начального и конечного кружков (они могут совпадать), M – количество отрезков, u_i и v_i – номера кружков, соединяемых i-м отрезком (направление стрелки – от u_i к v_i). Два кружка могут быть соединены не более чем одним отрезком. Все числа во входном файле являются целыми и разделяются пробелами и/или символами перевода строки.

Выходные данные
Вывести в выходной файл искомое количество очков и номера кружков, по которым должен пройти игрок, чтобы набрать это количество. Номера кружков должны быть записаны в порядке их посещения игроком. Если пройти из начального кружка в конечный, удовлетворяя правилам игры, невозможно, выходной файл должен содержать единственную строку «NO SOLUTION».

Пример входного файла
5 1 3 5 100 23
1 4
5
1 2
2 3
5 3
2 5
4 2

Пример выходного файла
-72
1 2 5 3 2 4

   Решение

Дано 27 монет, из которых одна фальшивая, причём фальшивая монета легче настоящей.
Как за три взвешивания на чашечных весах без гирь определить фальшивую монету?

   Решение

Страница: << 1 2 3 4 5 6 7 >> [Всего задач: 161]      

В вершинах шестиугольника ABCDEF (см. рис.) лежали 6 одинаковых на вид шариков: в A — массой 1 г, в B — 2 г, ..., в F — 6 г. Шутник поменял местами два шарика в противоположных вершинах. Имеются двухчашечные весы, позволяющие узнать, в какой из чаш масса шариков больше. Как за одно взвешивание определить, какие именно шарики переставлены?

Прислать комментарий

Решение

Дано 27 монет, из которых одна фальшивая, причём фальшивая монета легче настоящей.
Как за три взвешивания на чашечных весах без гирь определить фальшивую монету?

Прислать комментарий

Решение

В корзине лежат 13 яблок. Имеются весы, с помощью которых можно узнать суммарный вес любых двух яблок.
Придумайте способ выяснить за 8 взвешиваний суммарный вес всех яблок.

Прислать комментарий

Решение

Какие веса могут иметь три гири для того, чтобы с их помощью можно было взвесить любое целое число килограммов от 1 до 10 на чашечных весах (гири можно ставить на обе чашки)? Приведите пример.

Прислать комментарий

Решение

Имеются чашечные весы без гирь и 3 одинаковые по внешнему виду монеты, одна из которых фальшивая: она легче настоящих (настоящие монеты одного веса). Сколько надо взвешиваний, чтобы определить фальшивую монету? Решите ту же задачу в случаях, когда имеется 4 монеты и 9 монет.

Прислать комментарий

Решение

Страница: << 1 2 3 4 5 6 7 >> [Всего задач: 161]