Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 10.10.2011, 18:46   #1
Filia
 
Аватар для Filia
 
Регистрация: 13.09.2011
Сообщений: 8
Восклицание Не могу понять условие задачи!

Задано N интервалов (a_i, b_i) , a_i < b_i, на прямой.

Числа a_i и b_i целые и не превосходят по модудю 2'000'000'000.

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

Вход: В первой строке N (1 ≤ N ≤ 100000) Cледующие N строк содержат координаты концов интервалов. В каждой строке записано два числа a_i и b_i, разделённых пробелом.

Выход: Нужно вывести единственное число — искомое число способов. Известно, что это оно не превосходит 10^18

Пример1:
Вход#1
4
1 2
1 4
3 5
4 5

Выход#1
3

Пример2:
Вход#2
4
1 2
1 2
2 3
2 3

Выход#2
4

Что здесь имеется ввиду под способами? В ходе решения и проверки на специальном сайте выяснилось что у двух интервалов могут быть два способа. Это смутило. Изначально казалось чно нужно просто вывести количество не пересекающихся пар...

Последний раз редактировалось Filia; 10.10.2011 в 19:04.
Filia вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Не могу понять. mad_raven Общие вопросы C/C++ 10 11.10.2010 03:33
Сумма ряда (Pascal). Не могу понять смысл задачи :( DsDevis Помощь студентам 9 26.03.2009 01:16
не могу понять как решать задачи по паскалю! aiktz Помощь студентам 10 11.03.2009 16:43
Не могу понять как решить задачи. Нужна помощь Студент заочник Помощь студентам 9 30.12.2008 23:49