Каталог по темам

Задачи

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

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

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

Задача 102950

[Булевы функции ]

Тема:

[

Задачи на полный перебор

]

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

Булевой функцией называется функция, принимающая одно из логических значений TRUE или FALSE и зависящая от некоторого (быть может, нулевого) количества аргументов, каждый из которых также может принимать любое из значений TRUE или FALSE.

Любая булева функция однозначно задается своей таблицей истинности, в которой для каждого возможного набора значений аргументов указано значение функции. Например, x AND y – булева функция от двух аргументов. Ее таблица истинности выглядит так:

Если договориться, что наборы значений аргументов в таблице располагаются в лексикографическом порядке, то функция AND однозначно задается третьим столбцом таблицы – строкой 0001. Аналогично, каждой булевой функции от k аргументов можно поставить в соответствие строку из нулей и единиц длины 2^k.

Задан набор из N+1 булевой функции (f, f₁, f₂, ..., f_N). Напишите программу, которая определяет, можно ли функцию f выразить через функции f₁, f₂, ..., f_N, и если такие представления возможны, то находит кратчайшее по числу символов среди них.

Входные данные
В первой строке входного файла записано целое число N (1 ≤ N ≤ 9). Последующие N+1 строк содержат описания функций f, f₁, f₂, ..., f_N соответственно. Каждая из функций описывается строкой символов так, как указано выше. Число аргументов у функции f будет не более двух, а у остальных функций – не более трех.

Выходные данные
Первая строка выходного файла должна содержать искомое символьное представление, либо строку «Impossible», если такого представления не
существует. После функции с нулевым числом аргументов скобки не ставятся. Если у функции f один аргумент, то он обозначается x, а если два, то они обозначаются x и y.

Пример входного файла
2
1
1010
0

Пример выходного файла
f1(f2,f2)

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

Задача 102929

[Максимальный M-угольник ]

Тема:

[

Задачи на полный перебор

]

Сложность: 4-

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

Входные данные
В первой строке входного файла через пробел записаны два целых числа M и N (3 ≤ M ≤ N ≤ 10). Во второй строке перечислены N точек, каждая из которых задана парой своих координат. Координаты являются вещественными числами и разделяются пробелом.

Выходные данные
В первую строку выходного файла нужно вывести площадь искомого M-угольника, а во вторую – номера точек, являющихся вершинами этого M-угольника (в порядке обхода по или против часовой стрелки). Номера точек разделяются пробелом. Если вариантов решений несколько, то достаточно выдать любой из них. Если же ни один M-угольник с указанными свойствами построить невозможно, то выходной файл должен содержать единственное число 0.

Пример входного файла
3 4
0 0 0 1 1 0 1 1

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

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

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