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

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

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

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

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

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

Решение

По кругу расставлено несколько коробочек. В каждой из них может лежать один или несколько шариков (или она может быть пустой). За один ход разрешается взять все шарики из любой коробочки и разложить их, двигаясь по часовой стрелке, начиная со следующей коробочки, кладя в каждую коробочку по одному шарику.
  а) Докажите, что если на каждом следующем ходе шарики берут из той коробочки, в которую попал последний шарик на предыдущем ходе, то в какой-то момент повторится начальное размещение шариков.
  б) Докажите, что за несколько ходов из любого начального размещения шариков по коробочкам можно получить любое другое.

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

Решение

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