Игровое поле представляет собой 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

   Решение

Докажите, что инверсия переводит каждую окружность или прямую линию снова в окружность или прямую линию.

   Решение

В равнобедренной трапеции ABCD основания  AD = 12,  BC = 6,  высота равна 4. Диагональ AC делит угол BAD трапеции на две части. Какая из них больше?

   Решение

Биссектриса треугольника делит одну из его сторон на отрезки 3 см и 5 см. В каких границах изменяется периметр треугольника?

   Решение

Монету в 1 копейку обкатывают вокруг такой же монеты.
а) Сколько она сделает полных оборотов вокруг своей оси?
б) А если её будут обкатывать вокруг монеты в полдоллара?
(Напомним, что диаметр копейки - 15 мм, диаметр монеты в полдоллара - 30 мм.)

   Решение

Страница: << 11 12 13 14 15 16 17 >> [Всего задач: 188]      

Лена и Ира покупали на рынке виноград. Когда взвешивали Ленину покупку, весы показывали два килограмма, когда Ирину --- то три. Потом они вместе положили свой виноград на весы, и стрелка остановилась на 4,5 кг. Сколько на самом деле весили их покупки?

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

Решение

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

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

Решение

Даны русские слова: люк, яр, ель, лен, лезь. Определите, что получится, если звуки, из которых состоят эти слова, произнести в обратном порядке.

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

Решение

Монету в 1 копейку обкатывают вокруг такой же монеты.
а) Сколько она сделает полных оборотов вокруг своей оси?
б) А если её будут обкатывать вокруг монеты в полдоллара?
(Напомним, что диаметр копейки - 15 мм, диаметр монеты в полдоллара - 30 мм.)

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

Решение

Когда Буратино отправился на занятия ВМШ, папа Карло пообещал ему заплатить за первую правильно решенную задачу одну копейку, за вторую - две копейки, за третью - четыре, и т.д. За месяц Буратино получил 655 руб 35 коп. Сколько задач он решил?

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

Решение

Страница: << 11 12 13 14 15 16 17 >> [Всего задач: 188]