Страница:
<< 1 2 3 [Всего задач: 14]
|
[Ограда сада
]
|
|
Сложность: 4
|
Где-то в далеком царстве-государстве жил-поживал король. Он унаследовал
небольшое собрание редких и весьма ценных деревьев. Для того, чтобы
обезопасить свою коллекцию от злоумышленников, король приказал возвести
вокруг нее высокий забор. Главный королевский колдун был назначен
ответственным за исполнение этого поручения.
Увы! Колдун быстро обнаружил, что единственный подходящий материал
для постройки забора – это сами деревья. Другими словами, необходимо
срубить некоторые деревья для того, чтобы построить забор вокруг оставшихся.
Естественно, чтобы сберечь свою голову, колдун захотел минимизировать
стоимость срубленных деревьев. Он поднялся в свою башню и оставался там до
тех пор, пока не придумал наилучшее возможное решение.
Вы должны написать программу, решающую задачу, с которой столкнулся
главный королевский колдун. Постройте такое подмножество деревьев с
наименьшей суммарной стоимостью, что, срубив деревья из этого
подмножества, можно построить один забор, огораживающий все оставшиеся
деревья. Если существует более одного подмножества с минимальной
стоимостью, выберите то, в котором меньше деревьев.
Входные данные
В первой строке входного файла записано целое число N – количество
деревьев в королевском лесу (2 ≤ N ≤ 14). Деревья нумеруются
последовательными целыми числами от 1 до N. Каждая из последующих N
строк содержит четыре целых числа xi, yi, vi, li, описывающих очередное дерево.
(xi, yi) – это координаты дерева на плоскости, vi
– его стоимость, а li
– длина забора, который может быть построен из этого дерева. Все числа vi, li, а также
абсолютные величины xi
и yi
– целые числа из диапазона [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
Задача "Троллейбусы"
Троллейбусы одного маршрута проходят через остановку
каждые k (1<=k<=500) минут. Известны времена прихода пассажиров
на эту остановку. Если пассажир приходит на остановку в
момент прихода троллейбуса, то он успевает уехать на нем.
Напишите программу, которая бы определяла, во сколько должен пройти
первый троллейбус (это время от 0 до k-1), чтобы:
1) Суммарное время ожидания троллейбуса для всех пассажиров было минимально.
2) Максимальное из времен ожидания троллейбуса было минимально.
Входные данные
Во входном файле INPUT.TXT записано сначала число k, затем - число N
(0<=N<=100000). Затем идет N чисел, задающих времена прихода пассажиров
на остановку. Каждое из этих чисел - целое от 0 до 100000.
Выходные данные
В выходной файл OUTPUT.TXT запишите два числа,
являющиеся ответами на первый и второй вопросы задачи соответственно.
Если решений несколько, выведите любое из них.
Пример файла INPUT.TXT
100 5
0 210 99 551 99
Пример файла OUTPUT.TXT
10
51
Царь пообещал награду тому, кто сможет на каменистом пустыре посадить красивый фруктовый сад. Об этом узнали два брата. Старший смог выкопать 18 ям (см. рис. слева). Больше нигде не удалось, только все лопаты сломал. Царь рассердился и посадил его в темницу. Тогда младший брат Иван предложил разместить яблони, груши и сливы в вершинах равных треугольников (см. рис. справа), а остальные ямы засыпать.
Царь ответил так:
— Хорошо, если деревьев каждого вида будет ровно по три и они будут расти в вершинах равных треугольников, выйдет красиво. Но три вида — слишком мало. Если кроме яблонь, груш и слив будут ещё и абрикосы — отпущу брата. Если добавишь пятый вид — черешню — заплачу за работу. Мне ещё миндаль нравится, но шесть треугольников ты тут не сможешь разместить.
— А если смогу?
— Тогда проси чего хочешь!
Иван задумался, не получить ли заодно и полцарства. Подумайте и вы: разместите как можно больше видов деревьев в вершинах равных треугольников. (Равенство треугольников означает равенство всех его сторон и углов, то есть точное совпадение при наложении; треугольники можно поворачивать и переворачивать. В одной яме может расти только одно дерево.)
а) Мальвина разбила каждую грань куба 2×2×2 на единичные квадраты и велела Буратино в некоторых квадратах написать крестики, а в остальных нолики так, чтобы каждый квадрат граничил по сторонам с двумя крестиками и двумя ноликами. На рисунке показано, как Буратино выполнил задание (видно только три грани). Докажите, что Буратино ошибся.
б) Помогите Буратино выполнить задание правильно. Достаточно описать хотя бы одну верную расстановку.
Страница:
<< 1 2 3 [Всего задач: 14]
Фильтр
