Темы --> Информатика --> Алгоритмы
    Задачи на моделирование(78 задач)
    Арифметические алгоритмы(240 задач)
    Алгоритмы поиска(155 задач)
    Алгоритмы сортировки(194 задач)
    Динамическое программирование(355 задач)
    Алгоритмы на графах(319 задач)
    Перебор(154 задач)
    Игры и выигрышные стратегии(33 задач)
    Вычислительная геометрия(216 задач)
    Эвристические методы(30 задач)
    Алгоритмы на строках(45 задач)
    Пересечение множеств(10 задач)
    Жадный алгоритм(71 задач)
    Теория расписаний(5 задач)
    Обработка текста(31 задач)
    Дата и время(14 задач)
---> 2 задач <---
Источники --> Личные олимпиады --> Международные олимпиады --> 2005
    1 тур(3 задач)
    2 тур(3 задач)
Страница: 1 Отображать по:
#566
Сад
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
256 megabytes

Байтмен владеет красивейшим садом в Байттауне, в котором он посадил n роз. Пришло лето, и цветы выросли большими и красивыми. Байтмен понял, что он не в состоянии самостоятельно ухаживать за всеми розами, и решил нанять двух садовников в помощь. В этом случае ему нужно выбрать две прямоугольные области, чтобы каждый из садовников ухаживал за розами в одной их них. Области не должны пересекаться, и в каждой должно быть ровно \(k\) роз.

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

Сад представляет собой прямоугольник длиной \(l\) метров и шириной \(w\) метров, который разделен на \(l\)·\(w\) одинаковых единичных квадратов размером 1x1 метр каждый. Зафиксируем координатную систему так, чтобы оси координат были параллельны сторонам сада. Все квадраты имеют целые координаты (\(x\),\(y\)), удовлетворяющие ограничениям 1 <= \(x\) <= \(l\), 1 <= \(y\) <= \(w\). В каждом единичном квадрате может содержаться любое количество роз.

Стороны прямоугольных областей, которые выбираются, должны быть параллельны сторонам сада, а их угловые единичные квадраты – иметь целые координаты. Прямоугольная область с угловыми единичными квадратами (\(l_1\),\(w_1\)), (\(l_1\),\(w_2\)), (\(l_2\),\(w_1\)) и (\(l_2\),\(w_2\)) (для 1 <= \(l_1\) <= \(l_2\) <= \(l\) и 1 <= \(w_1\) <= \(w_2\) <= \(w\)):

• содержит все единичные квадраты с координатами (\(x\),\(y\)), которые удовлетворяют условию \(l_1\) <= \(x\) <= \(l_2\) и \(w_1\) <= \(y\) <= \(w_2\), и
• имеет периметр 2 · (\(l_2\)−\(l_1\)+1)+ 2 · (\(w_2\)−\(w_1\)+1).

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

Задание

Напишите программу, которая:

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

Входные данные

Первая строка стандартного ввода содержит два числа: \(l\) и \(w\) (1 <= \(l\),\(w\) <= 250), разделенных одним пробелом – длину и ширину сада. Во второй строке задаются два числа: \(n\) и \(k\) (2 <= \(n\) <= 5000, 1 <= \(k\) <= \(n\)/2), записанных через пробел и обозначающих общее количество роз в саду и количество роз, которое должно быть в каждой из прямоугольных областей. Следующие \(n\) строк содержат позиции роз, по одной розе в строке. Каждая (\(i\)+2)-я строка содержит два числа \(l_i\), \(w_i\) (1 <= \(l_i\) <= \(l\), 1 <= \(w_i\) <= \(w\)), разделенных одним пробелом – координаты квадрата, содержащего \(i\)-ю розу.

В одном квадрате может содержаться две или большее количество роз.

Выходные данные

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

Примеры
Входные данные
6 5
7 3
3 4
3 3
6 1
1 1
5 5
5 5
3 1
Выходные данные
22
#571
Реки
  

Почти все Королевство Байтленд покрыто лесами и реками. Малые реки сливаются в более крупные реки, которые, в свою очередь, сливаются друг с другом; в конечном счете, все реки сливаются вместе в одну большую реку. Большая река впадает в море вблизи города Байттаун.

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

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

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

Задание

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

Входные данные

Первая строка входных данных содержит два целых числа: \(n\) — количество поселков, не считая Байттауна (2 ≤ \(n\) ≤ 100), и \(k\) — количество дополнительных пилорам, которые будут установлены (1 ≤ \(k\) ≤ 50 и \(k\) ≤ \(n\) ). Поселки нумеруются числами 1 , 2 , ...., n , а Байттаун имеет номер 0.

Каждая из последующих n строк содержит три целых числа, разделенных одним пробелом. Строка i + 1 содержит:

\(w_i\) — количество деревьев, срубаемых в поселке \(i\) за год (0 ≤ \(w_i\) ≤ 10 000),
\(v_i\) — ближайший поселок (либо Байттаун) вниз по реке от поселка \(i\) (0 ≤ \(v_i\) ≤ \(n\) ),
\(d_i\) — расстояние (в километрах) по реке от поселка \(i\) до поселка \(v_i\) (1 ≤ \(d_i\) ≤ 10 000).
Гарантируется, что суммарная стоимость сплава всех деревьев к пилораме в Байттауне не превосходит 2 000 000 000 центов в год.
В 50% тестов число n не превосходит 20.

Выходные данные

Первая и единственная строка выходных данных должна содержать одно целое число: минимальную стоимость сплава (в центах).

Пояснения

Рисунок сверху иллюстрирует входные данные примера. Номера поселков указаны внутри кругов. Числа под кругами обозначают количество деревьев, срубаемых вблизи данного поселка. Числа над стрелками указывают длины рек.

Пилорамы должны быть установлены в поселках 2 и 3.

Примеры
Входные данные
4 2
1 0 1
1 1 10
10 2 5
1 2 3
Выходные данные
4
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест