ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Фильтр
Сложность с по   Класс с по  
Выбрана 1 задача
Версия для печати
Убрать все задачи

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

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

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

Входной файл содержит исходные данные в следующей последовательности: N, x1, x2, ..., xN, b, q, M, u1, v1, u2, v2, ..., uM, vM. Здесь N – количество кружков (1 ≤ N ≤ 30), xi – стоимость, приписанная i-му кружку (1 ≤ xi ≤ 30 000), b и q – номера начального и конечного кружков (они могут совпадать), M – количество отрезков, ui и vi – номера кружков, соединяемых i-м отрезком (направление стрелки – от ui к vi). Два кружка могут быть соединены не более чем одним отрезком. Все числа во входном файле являются целыми и разделяются пробелами и/или символами перевода строки.

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

Вывести в выходной файл искомое количество очков и номера кружков, по которым должен пройти игрок, чтобы набрать это количество. Номера кружков должны быть записаны в порядке их посещения игроком. Если пройти из начального кружка в конечный, удовлетворяя правилам игры, невозможно, выходной файл должен содержать единственную строку «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

   Решение

Задачи

Страница: << 5 6 7 8 9 10 11 >> [Всего задач: 67]      



Задача 102921

 [Треугольники ]
Темы:   [ Перебор с отсечениями ]
[ Треугольники ]
Сложность: 3+

На плоскости отмечено N = 3K точек. Будем рассматривать такие варианты построения K невырожденных треугольников с вершинами в этих точках, при которых каждая из заданных точек является вершиной какого-либо треугольника. Точки расположены так, что хотя бы одно построение с указанным свойством существует. Требуется определить тот вариант, при котором суммарная площадь полученных K треугольников минимальна.

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

Во входном файле содержатся (в указанном порядке) целое число N (1 ≤ N ≤ 30) и N пар вещественных чисел, задающих координаты точек. Числа разделяются пробелами и/или символами перевода строки.

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

Первая строка выходного файла должна содержать минимально возможное значение суммарной площади. В каждую из следующих K строк запишите тройку номеров вершин, образующих очередной из треугольников. Номера вершин разделяются пробелом.

Пример входного файла

6
0 0
1 0
10 0
0 2
12 0
10 1

Пример выходного файла

2
1 2 4
3 5 6
Прислать комментарий     Решение


Задача 102922

 [Идем кругами ]
Темы:   [ Перебор с отсечениями ]
[ Эйлеров цикл ]
Сложность: 3+

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

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

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

Входной файл содержит исходные данные в следующей последовательности: N, x1, x2, ..., xN, b, q, M, u1, v1, u2, v2, ..., uM, vM. Здесь N – количество кружков (1 ≤ N ≤ 30), xi – стоимость, приписанная i-му кружку (1 ≤ xi ≤ 30 000), b и q – номера начального и конечного кружков (они могут совпадать), M – количество отрезков, ui и vi – номера кружков, соединяемых i-м отрезком (направление стрелки – от ui к vi). Два кружка могут быть соединены не более чем одним отрезком. Все числа во входном файле являются целыми и разделяются пробелами и/или символами перевода строки.

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

Вывести в выходной файл искомое количество очков и номера кружков, по которым должен пройти игрок, чтобы набрать это количество. Номера кружков должны быть записаны в порядке их посещения игроком. Если пройти из начального кружка в конечный, удовлетворяя правилам игры, невозможно, выходной файл должен содержать единственную строку «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
Прислать комментарий     Решение


Задача 102923

 [Круги ]
Тема:   [ Задачи на полный перебор ]
Сложность: 3+

Задан круг, разделенный на N секторов, и два целых числа M и K. В каждый из секторов круга помещается одно целое число, не меньшее K. Когда секторы заполнены числами, из них можно получать новые числа по следующим правилам:
    взять число из одного сектора;
    взять число, равное сумме двух или более чисел в смежных секторах.
Из новых чисел составляется наибольшая последовательность подряд идущих чисел, начинающаяся с числа M: (M, M+1, M+2, ..., I).

Пример на рисунке показывает, как получить все новые числа от 2 до 21 для приведенных на нем чисел в секторах. Серым цветом выделены суммируемые числа.


Напишите программу, которая определяет способ расстановки чисел в секторах, максимизирующий длину указанной последовательности.

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

Входной файл содержит три целых числа N, M и K (N ≤ 6, M ≤ 20, 0 ≤ K ≤ 20).

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

Выведите в первую строку выходного файла наибольшее число I для неразрывной последовательности новых чисел от M до I, которая может быть получена из чисел в секторах. Далее выведите все наборы чисел в секторах, из которых можно получить такую последовательность. Каждый набор записывается в отдельную строку выходного файла в виде списка чисел, начинающегося с наименьшего из них (оно может быть не единственным). Числа в списке должны идти в том же порядке, в котором они записаны в секторах круга. Если наименьшее число встречается несколько раз, следует вывести все возможные комбинации. Например, (1 1 2 3), (1 2 3 1), (1 3 2 1) и (1 1 3 2).

Пример входного файла

5
2
1

Пример выходного файла

21
1 3 10 2 5
1 5 2 10 3
2 4 9 3 5
2 5 3 9 4
Прислать комментарий     Решение


Задача 102935

 [Пересечение многоугольников ]
Темы:   [ Прямая и отрезок ]
[ Площадь ]
Сложность: 3+

Два многоугольника на плоскости заданы координатами своих вершин. Требуется вычислить площадь пересечения этих многоугольников, то есть сумму площадей тех кусков, которые образуются при их пересечении и принадлежат каждому из них. При этом вы можете предполагать, что: 
    А) Многоугольники выпуклые, а координаты их вершин даны в произвольном порядке.
    Б) Хотя бы один из многоугольников невыпуклый, но известно, что у каждого из многоугольников не более одного угла, большего 180 градусов, а координаты вершин даны в порядке обхода по часовой стрелке.
Ваша программа по входным данным должна сама определить, какой из этих двух случаев имеет место.

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

Первая строка входного файла содержит целое число N – количество вершин в первом многоугольнике (3 ≤ N ≤ 50). Во второй строке записаны координаты этих вершин. Третья и четвертая строки таким же образом задают второй многоугольник. Координаты всех вершин являются целыми числами из диапазона [-32768, 32767].

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

Выведите в выходной файл искомую площадь не менее чем с 6 верными значащими цифрами.

Пример входного файла

3
0 3 0 -3 -3 0
5
-1 1 2 1 1 0 2 -1 -1 -1

Пример выходного файла

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


Задача 102936

 [Пересечение окружностей ]
Тема:   [ Круги и окружности ]
Сложность: 3+

На плоскости провели N окружностей. Требуется определить площадь их пересечения.

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

В первой строке входного файла находится целое число N (1 ≤ N ≤ 20). В каждой из последующих N строк записана тройка вещественных чисел, описывающих очередную из окружностей. Первые два числа задают координаты ее центра, третье – радиус.

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

Выведите в выходной файл искомую площадь не менее чем с 6 верными значащими цифрами.

Пример входного файла

2
0 0 1
1 1 1

Пример выходного файла

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


Страница: << 5 6 7 8 9 10 11 >> [Всего задач: 67]      



© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .