Версия для печати
Убрать все задачи

---

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

   Решение

---

Каких чисел больше среди натуральных чисел от 1 до 1000000 включительно: представимых в виде суммы точного квадрата и точного куба или не представимых в таком виде?

   Решение

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

по 1 по 2 по 5 по 10 по 20 по 50 по 100   с решениями  

---

Задача 109631  (#96.5.9.1)

Темы:   [ Задачи с ограничениями ] [ Правило произведения ]

Сложность: 3 Классы: 9

Каких чисел больше среди натуральных чисел от 1 до 1000000 включительно: представимых в виде суммы точного квадрата и точного куба или не представимых в таком виде?

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

Решение

---

Задача 109632  (#96.5.9.2)

Темы:   [ Две касательные, проведенные из одной точки ] [ Три окружности одного радиуса ]

Сложность: 3+ Классы: 8,9

Центры O₁ , O₂ и O₃ трех непересекающихся окружностей одинакового радиуса расположены в вершинах треугольника. Из точек O₁ , O₂ и O₃ проведены касательные к данным окружностям так, как показано на рисунке. Известно, что эти касательные, пересекаясь, образовали выпуклый шестиугольник, стороны которого через одну покрашены в красный и синий цвета. Докажите, что сумма длин красных отрезков равна сумме длин синих отрезков.

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

Решение

---

Задача 109633  (#96.5.9.3)

Темы:   [ Уравнения в целых числах ] [ Основная теорема арифметики. Разложение на простые сомножители ] [ НОД и НОК. Взаимная простота ]

Сложность: 4+ Классы: 8,9,10

Пусть натуральные числа x, y, p, n и k таковы, что   xⁿ + yⁿ = p^k.
Докажите, что если число n  (n > 1)  нечётно, а число p нечётное простое, то n является степенью числа p (с натуральным показателем).

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

Решение

---

Задача 109634  (#96.5.9.4)

Темы:   [ Объединение, пересечение и разность множеств ] [ Подсчет двумя способами ] [ Классическая комбинаторика (прочее) ] [ Классические неравенства (прочее) ]

Сложность: 5 Классы: 8,9,10

В Думе 1600 депутатов, которые образовали 16000 комитетов по 80 человек в каждом.
Докажите, что найдутся два комитета, имеющие не менее четырёх общих членов.

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

Решение

---

Задача 109635  (#96.5.9.5)

Темы:   [ Арифметическая прогрессия ] [ Разложение на множители ] [ Делимость чисел. Общие свойства ] [ Признаки делимости на 3 и 9 ]

Сложность: 4- Классы: 9,10

Докажите, что в арифметической прогрессии с первым членом, равным 1, и разностью, равной 729, найдётся бесконечно много членов, являющихся степенью числа 10.

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

Решение

---

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

по 1 по 2 по 5 по 10 по 20 по 50 по 100   с решениями