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

Задачи

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

Задача 102921 (#1)

[Треугольники ]

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

Сложность: 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 (#2)

[Идем кругами ]

Темы:	[	Перебор с отсечениями	]
Темы:	[	Эйлеров цикл	]

Сложность: 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)

[Круги ]

Тема:

[

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

]

Сложность: 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

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

Задача 102925 (#5)

[Испытание шаха ]

Тема:

[

Перебор с отсечениями

]

Сложность: 3

Известна легенда, что в древней Лимонии любой претендент на должность визиря при шахе должен был выдержать следующее испытание. Ему дается доска размером M × M и некоторое количество шахматных фигур: ферзей, ладей, слонов, коней и королей. Претендент должен расставить их на доске таким образом, чтобы ни одна из фигур не била другие фигуры, и все фигуры были выставлены на доске. Если претендент выдерживал испытание, он назначался визирем, а если не выдерживал... то не назначался. Напишите программу, которая будет решать эту головоломку.

Входные данные
Первое число во входном файле задает размер доски M (2 ≤ M ≤ 12). Следующие 5 целых неотрицательных чисел K, Q, R, B, N задают соответственно количество королей, ферзей, ладей, слонов и коней, которые требуется расставить. Общее количество фигур не превосходит M² . Фигуры подобраны так, что искомая расстановка существует.

Выходные данные
Вывести в выходной файл доску с расставленными фигурами в виде M строк по M символов в каждой. Пустые поля обозначаются символом . (точка), поля с королями – K, ферзями – Q, ладьями – R, слонами – B, конями – N.

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

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

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

Задача 102926 (#6)

[Ребус ]

Тема:

[

Перебор с отсечениями

]

Сложность: 3

Арифметический ребус – это зашифрованная запись сложения двух натуральных чисел (например, КОМП+КОМП=СБОРЫ). При этом одинаковым буквам должны соответствовать одинаковые цифры, разным – разные, и ни одно из чисел не может начинаться с нуля. Требуется написать программу, находящую все возможные решения такого ребуса.

Входные данные
Входной файл содержит единственную строку с записью ребуса. Длина строки не превышает 30 символов.

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

Пример входного файла
ЛЕТО+ЛЕТО=ПОЛЕТ

Пример выходного файла
1
8947+8947=17894

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

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