Страница:
<< 2599 2600 2601 2602
2603 2604 2605 >> [Всего задач: 21755]
|
[Иванушка и царевна
]
|
|
Сложность: 3+ |
Царевна стоит в центре болота и громко плачет. Злой Кощей привязал ее к
столбу веревкой так, что веревка обмоталась вокруг царевны ровно I раз по
часовой стрелке. Иванушка хочет освободить царевну и взять ее в жены.
Проблема заключается в том, что плавать в болоте невозможно и ему
приходится прыгать по кочкам. При каждом таком прыжке за ноги Иванушки
зацепляется определенное количество зеленых водорослей.
Будем считать, что поверхность болота ровная, а веревка достаточно
длинная и не может ни за что зацепиться либо запутаться. Иванушка должен,
держа в руках конец этой веревки, проскакать по кочкам так, чтобы размотать
царевну и вернуться на начальную кочку. Так как царевна очень изнежена, то
она ни в какой момент времени не должна быть обмотана веревкой более десяти
раз (иначе веревка поранит царевну).
Требуется определить такой маршрут движения Иванушки, при котором за
его ноги зацепится минимально возможное количество водорослей.
Входные данные
Первая строка входного файла содержит три целых числа: N – количество
кочек в болоте (3 ≤ N ≤ 10), I – количество оборотов веревки (1 ≤ I ≤ 6) и S – номер
кочки, на которой в начальный момент стоит Иванушка
(1 ≤ S ≤ N). Каждая из
следующих N строк содержит вещественные координаты одной из кочек,
записанные через пробел. Известно, что никакой отрезок, соединяющий две
кочки, не проходит через центр болота, имеющий по соглашению координаты
(0, 0).
В следующих N строках записана матрица N × N, составленная из
вещественных чисел. Число в i-й строке и j-м столбце этой матрицы означает
количество водорослей, цепляющихся за ноги Иванушки при прыжке с i-й
кочки на j-ю.
Выходные данные
В первую строку выходного файла выведите минимально возможное
количество водорослей, которые зацепятся за ноги Иванушки, с точностью до
двух знаков после десятичной точки. Во вторую строку запишите
соответствующий маршрут Иванушки, заданный номерами кочек, по которым
он должен проскакать. Номера кочек разделяются пробелом.
Пример входного файла
3 1 1
-1 0
0 1
1 -2
0 1 1
1 0 1
1 1 0
Пример выходного файла
3.00
1 3 2 1
|
[Покрытие путями
]
|
|
Сложность: 3+ |
Задан ориентированный ациклический граф. Требуется построить наименьшее
количество путей, покрывающих все вершины этого графа и не пересекающихся
ни по одной из вершин.
Входные данные
В первой строке входного файла записано количество вершин графа N
(1 ≤ N ≤ 25). Далее перечислены ребра графа, заданные номерами начальной и
конечной вершин.
Выходные данные
Выведите в первую строку выходного файла число K – наименьшее количество
путей, которыми можно покрыть все вершины графа. Далее выведите сами эти
пути (по одному в каждой строке), задавая их номерами вершин в порядке
посещения.
Пример входного файла
4
1 2
1 3
2 3
2 4
Пример выходного файла
2
1 2 4
3
|
[Сопротивление
]
|
|
Сложность: 3+ |
Задана электрическая схема из некоторого количества узлов и N резисторов, их
соединяющих. Напишите программу, вычисляющую сопротивление между
двумя заданными узлами A и B этой схемы. Допускается частичное решение
задачи для случая параллельно-последовательных схем.
Пояснения для тех, кто плохо учил в школе физику:
1. Сила тока равна напряжению, поделенному на сопротивление: I = U
/
R.
2. Сумма токов, втекающих в узел, равна сумме токов, вытекающих из него.
3. Сумма падений напряжений I · R на отдельных участках произвольного
замкнутого контура равна сумме всех ЭДС в этом контуре.
Как следствие, получаем следующие формулы:
1. При последовательном соединении резисторов с сопротивлениями R1
и R2 общее сопротивление R вычисляется по формуле R = R1
+
R2;
2. При параллельном соединении резисторов с сопротивлениями R1
и R2
общее сопротивление R вычисляется по формуле 1
/
R = 1
/
R1
+
1
/
R2.
Входные данные
В первой строке входного файла содержится целое число N – количество
резисторов в схеме (1 ≤ N ≤ 50). Во второй строке записаны номера узлов A и B
(узлы нумеруются начиная с 1). Каждая из следующих N строк содержит
описание очередного резистора в виде тройки целых чисел из диапазона
[0, 32767], записанных через пробел. Первые два числа задают номера двух
различных узлов схемы, которые этот резистор соединяет, а третье – его
сопротивление. Между двумя узлами схемы могут располагаться несколько
резисторов.
Выходные данные
Выведите в выходной файл искомое сопротивление не менее чем с 6 верными
значащими цифрами.
Пример входного файла
4
1 2
1 3 1
3 4 1
4 3 1
2 4 1
Пример выходного файла
2.50
|
[Треугольники
]
|
|
Сложность: 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
|
[Идем кругами
]
|
|
Сложность: 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
Страница:
<< 2599 2600 2601 2602
2603 2604 2605 >> [Всего задач: 21755]