Каталог по источникам

Задачи

Страница: << 18 19 20 21 22 23 24 >> [Всего задач: 145]

Задача 102900

[Сопротивление ]

Тема:

[

Линейная алгебра

]

Сложность: 3+

Задана электрическая схема из некоторого количества узлов и N резисторов, их соединяющих. Напишите программу, вычисляющую сопротивление между двумя заданными узлами A и B этой схемы. Допускается частичное решение задачи для случая параллельно-последовательных схем.

Пояснения для тех, кто плохо учил в школе физику:
    1. Сила тока равна напряжению, поделенному на сопротивление: I = U / R.
    2. Сумма токов, втекающих в узел, равна сумме токов, вытекающих из него.
    3. Сумма падений напряжений I · R на отдельных участках произвольного замкнутого контура равна сумме всех ЭДС в этом контуре.

Как следствие, получаем следующие формулы:
    1. При последовательном соединении резисторов с сопротивлениями R₁ и R₂ общее сопротивление R вычисляется по формуле R = R₁ + R₂;
    2. При параллельном соединении резисторов с сопротивлениями R₁ и R₂ общее сопротивление R вычисляется по формуле 1 / R = 1 / R₁ + 1 / R₂.

Входные данные
В первой строке входного файла содержится целое число 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

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

Задача 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, 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

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

Задача 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

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

Страница: << 18 19 20 21 22 23 24 >> [Всего задач: 145]