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

   Решение

Можно ли поместить правильный треугольник внутрь правильного шестиугольника так, чтобы из любой вершины шестиугольника были видны все три вершины треугольника? (Точка $A$ видна из точки $B$, если отрезок $AB$ не содержит внутренних точек треугольника.)

   Решение

Глава Монетного двора хочет выпустить монеты 12 номиналов (каждый – в натуральное число рублей) так, чтобы любую сумму от 1 до 6543 рублей можно было заплатить без сдачи, используя не более 8 монет. Сможет ли он это сделать?
(При уплате суммы можно использовать несколько монет одного номинала.)

   Решение

Страница: 1 2 >> [Всего задач: 10]      

Основание пирамиды – равнобедренный треугольник с основанием 6 и высотой 9. Каждое боковое ребро равно 13. Найдите объём пирамиды.

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

Решение

В треугольной пирамиде, каждое боковое ребро которой равно a , один плоский угол при вершине прямой, а каждый из остальных равен 60^o . Найдите объём пирамиды.

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

Решение

Существует ли тетраэдр ABCD, в котором  AB = AC = AD = BC,  а суммы плоских углов при каждой из вершин В и С равны по 150°?

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

Решение

В тетраэдре АВСD:  АВ = 8,  ВС = 10,  АС = 12,  BD = 15.  Известно, что четыре отрезка, соединяющие вершины тетраэдра с центрами окружностей, вписанных в противолежащие грани, пересекаются в одной точке. Найдите длины рёбер DA и DC.

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

Решение

Даны два тетраэдра. Ни у одного из них нет двух подобных граней, но каждая грань первого тетраэдра подобна какой-то грани второго.
Обязательно ли эти тетраэдры подобны?

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

Решение

Страница: 1 2 >> [Всего задач: 10]