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

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

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

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

   Решение

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

На плоскости дано n3 точек, причем не все они лежат на одной прямой. Докажите, что существует окружность, проходящая через три из данных точек и не содержащая внутри ни одной из оставшихся точек.

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

Решение

На плоскости расположено несколько точек, все попарные расстояния между которыми различны. Каждую из этих точек соединяют с ближайшей. Может ли при этом получиться замкнутая ломаная?

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

Решение

Докажите, что по крайней мере одно из оснований перпендикуляров, опущенных из внутренней точки выпуклого многоугольника на его стороны, лежит на самой стороне, а не на ее продолжении.

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

Решение

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

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

Решение

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

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

Решение

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