|
Модераторы: Poseidon |
|
Sanya |
|
|||
Новичок Профиль Группа: Участник Сообщений: 8 Регистрация: 7.10.2006 Репутация: 1 Всего: 1 |
Минимальное покрытие
Ограничение времени: 1.0 секунды Ограничение памяти: 16 МБ Среди заданного множества отрезков прямой с целочисленными координатами концов [ Li , Ri ] необходимо выбрать подмножество наименьшей мощности, целиком покрывающее отрезок [0,M], где M – натуральное число. Исходные данные В первой строке указана константа M (1 <= M <= 5000). В последующих строках перечислены пары чисел "Li Ri" (abs(Li), abs(Ri) <= 50000), каждая пара с новой строки, числа в парах отделены друг от друга одним или несколькими пробелами. Список завершается парой чисел "0 0". i <= 100000 Результат Программа должна формировать в первой строке требуемое минимальное число отрезков из исходного множества, необходимое для покрытия отрезка [0,M]. Далее должен следовать список покрывающего подмножества, упорядоченный по возрастанию координат левых концов отрезков. Список отрезков выводится в том же формате, что и во входe, завершающую пару [0,0] выводить не следует. Если покрытие отрезка [0,M] исходным множеством отрезков [Li,Ri] невозможно, то соледует вывести единственную фразу "No solution". Пример исходных данных Sample input #1 1 -1 0 -5 -3 2 5 0 0 Sample input #2 1 -1 0 0 1 0 0 Пример результата Sample output #1 No solution Sample output #2 1 0 1 |
|||
|
||||
maxim1000 |
|
|||
Эксперт Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: 24 Всего: 110 |
можно попробовать вариацию на тему динамического программирования:
для начала рассматриваем "полупокрытия" (термин, придуманный только что): полупокрытие - подмножество отрезков, которое полностью покрывает отрезок [0,x], x<=M цель задачи - полупокрытие для x=M далее алгоритм такой: 1. ищем полупокрытие из одного отрезка, для максимально возможного x1 2. ищем полупокрытие из двух отрезков для максимально возможного x2 и т.д., пока очередной x не будет равен M фишка в том, что для получения результатов каждого следующего шага можно использовать результаты предыдущего, из-за этого, по идее, должно шустренько работать алгоритм каждого следующего шага: 1. перебираем все неиспользованные отрезки, у которых левый конец находится левее правого конца полупокрытия с предущего шага 2. из них выбираем тот, к которого правая граница наибольшая Добавлено @ 19:54 P.S. ну если не останется неиспользованных отрезков, а правый конец полупокрытия не доберётся до M, значит, нет решений -------------------- qqq |
|||
|
||||
Правила форума "Центр помощи" | |
ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Более подробно с правилами данного раздела Вы можете ознакомится в этой теме. Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman |
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | Центр помощи | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |