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

Задачи

Страница: << 23 24 25 26 27 28 29 >> [Всего задач: 145]

Задача 102928

[Ограда сада ]

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

Сложность: 4

Где-то в далеком царстве-государстве жил-поживал король. Он унаследовал небольшое собрание редких и весьма ценных деревьев. Для того, чтобы обезопасить свою коллекцию от злоумышленников, король приказал возвести вокруг нее высокий забор. Главный королевский колдун был назначен ответственным за исполнение этого поручения.

Увы! Колдун быстро обнаружил, что единственный подходящий материал для постройки забора – это сами деревья. Другими словами, необходимо срубить некоторые деревья для того, чтобы построить забор вокруг оставшихся. Естественно, чтобы сберечь свою голову, колдун захотел минимизировать стоимость срубленных деревьев. Он поднялся в свою башню и оставался там до тех пор, пока не придумал наилучшее возможное решение.

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

Входные данные
В первой строке входного файла записано целое число N – количество деревьев в королевском лесу (2 ≤ N ≤ 14). Деревья нумеруются
последовательными целыми числами от 1 до N. Каждая из последующих N строк содержит четыре целых числа x_i, y_i, v_i, l_i, описывающих очередное дерево. (x_i, y_i) – это координаты дерева на плоскости, v_i – его стоимость, а l_i – длина забора, который может быть построен из этого дерева. Все числа v_i, l_i, а также абсолютные величины x_i и y_i – целые числа из диапазона [0, 10000]. Считается, что деревья имеют нулевой радиус.

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

Пример входного файла
6
0 0 8 3
1 4 3 2
2 1 7 1
4 1 2 3
3 5 4 6
2 3 9 8

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

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

Задача 102938

[Путь на параллелепипеде ]

Тема:

[

Задачи в пространстве

]

Сложность: 4

На поверхности прямоугольного параллелепипеда { (x, y, z) | 0 ≤ x ≤ L, 0 ≤ y ≤ W, 0 ≤ z ≤ H } отмечены две точки с координатами (x₁, y₁, z₁) и (x₂, y₂, z₂). Существует много путей, проходящих по поверхности параллелепипеда и соединяющих заданные точки. Требуется найти квадрат длины кратчайшего из таких путей.

Входные данные
Файл входных данных содержит (в указанном порядке) следующие 9 целых чисел: L, W, H, x₁, y₁, z₁, x₂, y₂, z₂ . Числа разделяются пробелами и/или символами перевода строки. Каждое из чисел L, W, H не превышает 100.

Выходные данные
Вывести в выходной файл одно целое число – квадрат длины искомого пути.

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

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

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

Задача 102940

[Вписанный, описанный и записанный ]

Тема:

[

Вычислительная геометрия (прочее)

]

Сложность: 4

Военный полигон имеет форму N-угольника и обнесен по границе забором. Военные изобрели атомную бомбу очередного поколения и намереваются провести испытания этого нового вида оружия. Узнав о планах «зеленых» помешать испытаниям, главнокомандующий приказал установить сверхсовременный пеленгатор, обнаруживающий посторонних в радиусе его действия.

У военных есть вполне естественное желание взорвать как можно более мощную атомную бомбу. При этом заместитель командира части по тылу настаивает, что забор полигона должен остаться целым. Тот же самый рачительный зам. по тылу хочет сэкономить как можно больше денег на электроэнергии, установив пеленгатор минимального радиуса действия, контролирующий весь полигон. Чтобы его не украли «зеленые», пеленгатор нужно установить на территории полигона. Напишите программу, определяющую минимальный радиус действия и точку установки пеленгатора, а также максимальный радиус поражения бомбы и точку ее взрыва.

Входные данные
Входной файл содержит вещественные координаты вершин N-угольника (1 ≤ N ≤ 50), записанные в порядке обхода по (или против) часовой стрелки.

Выходные данные
Запишите в выходной файл искомые координаты и радиусы действия в соответствии с форматом, приведенным в примере.

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

Пример выходного файла
Установить пеленгатор в точке (5, 5) радиусом действия 7.0710678
Взорвать бомбу в точке (5, 5) радиусом действия 5.0000000

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

Задача 102944

[Отравленный пирог ]

Темы:	[	Динамическое программирование в игровых задачах	]
Темы:	[	Построение перечислителя	]

Сложность: 4

Для игры «Отравленный пирог» используется прямоугольный пирог, разделенный на M «строк» горизонтальными разрезами и на N «столбцов» – вертикальными. Таким образом, пирог должен быть разбит на M × N клеток, правая нижняя из которых «отравлена». Играют двое игроков, ходы делаются по очереди. Каждый ход заключается в том, что игрок выбирает одну из еще не съеденных клеток пирога и съедает все клетки, расположенные левее и выше выбранной (в том числе и выбранную). Проигрывает тот, кто съедает отравленную клетку.

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

Входные данные
Данные во входном файле расположены в следующем порядке: M, N (1 ≤ M, N ≤ 9), X₁, ..., X_M. Здесь X_i – число оставшихся клеток в i-м снизу горизонтальном ряду. Все числа во входном файле разделяются пробелами и/или символами перевода строки.

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

Каждый ход задается парой чисел (i, j), где i – номер (снизу) горизонтального ряда, а j – номер (справа) вертикального ряда, которому принадлежит выбранная клетка (1 ≤ i ≤ M, 1 ≤ j ≤ N).

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

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

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

Задача 102947

[Острова ]

Тема:

[

Неопределено

]

Сложность: 4

Генератор случайных карт известной игры Heroes of Might and Magic III создает острова, на которых изначально будут расположены герои. При такой генерации острова получаются различными по величине. Назовем коэффициентом несправедливости отношение площади наибольшего острова к площади наименьшего. Требуется определить этот коэффициент.

Карта задается прямоугольником N × M, в каждой клетке которого записана цифра 0 (вода) или цифра 1 (земля). Островом считается максимальное связное множество клеток, содержащих единички, т.е. такое множество клеток A, что:
    из любой клетки A можно пройти до любой другой клетки A, переходя лишь через клетки A и их стороны;
    при добавлении к A любой другой клетки, содержащей 1, предыдущее условие нарушается.

Входные данные
В первой строке входного файла содержатся числа N и M – размеры карты (1 ≤ N, M ≤ 1000). Далее записана сама карта – M строк по N чисел (0 или 1) в каждой. Числа внутри строки разделяются пробелом.

Выходные данные
В выходной файл вывести коэффициент несправедливости с 5 знаками после десятичной точки. Если на карте нет ни одного острова, вывести 0.

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

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

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

Страница: << 23 24 25 26 27 28 29 >> [Всего задач: 145]