ЗАДАЧИ
problems.ru |
О проекте
|
Об авторах
|
Справочник
Каталог по темам | по источникам | |
|
Подтемы:
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Версия для печати
Убрать все задачи Где-то в далеком царстве-государстве жил-поживал король. Он унаследовал небольшое собрание редких и весьма ценных деревьев. Для того, чтобы обезопасить свою коллекцию от злоумышленников, король приказал возвести вокруг нее высокий забор. Главный королевский колдун был назначен ответственным за исполнение этого поручения. Увы! Колдун быстро обнаружил, что единственный подходящий материал для постройки забора – это сами деревья. Другими словами, необходимо срубить некоторые деревья для того, чтобы построить забор вокруг оставшихся. Естественно, чтобы сберечь свою голову, колдун захотел минимизировать стоимость срубленных деревьев. Он поднялся в свою башню и оставался там до тех пор, пока не придумал наилучшее возможное решение. Вы должны написать программу, решающую задачу, с которой столкнулся
главный королевский колдун. Постройте такое подмножество деревьев с
наименьшей суммарной стоимостью, что, срубив деревья из этого
подмножества, можно построить один забор, огораживающий все оставшиеся
деревья. Если существует более одного подмножества с минимальной
стоимостью, выберите то, в котором меньше деревьев.
|
Страница: << 1 2 3 [Всего задач: 14]
Увы! Колдун быстро обнаружил, что единственный подходящий материал для постройки забора – это сами деревья. Другими словами, необходимо срубить некоторые деревья для того, чтобы построить забор вокруг оставшихся. Естественно, чтобы сберечь свою голову, колдун захотел минимизировать стоимость срубленных деревьев. Он поднялся в свою башню и оставался там до тех пор, пока не придумал наилучшее возможное решение. Вы должны написать программу, решающую задачу, с которой столкнулся
главный королевский колдун. Постройте такое подмножество деревьев с
наименьшей суммарной стоимостью, что, срубив деревья из этого
подмножества, можно построить один забор, огораживающий все оставшиеся
деревья. Если существует более одного подмножества с минимальной
стоимостью, выберите то, в котором меньше деревьев.
Задача "Троллейбусы" Троллейбусы одного маршрута проходят через остановку каждые 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] |
© 2004-...
МЦНМО
(о копирайте)
|
Пишите нам
|