![]() |
|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
![]() |
|
Опции темы | Поиск в этой теме |
![]() |
#1 |
Регистрация: 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. |
![]() |
![]() |
![]() |
![]() |
||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Не могу понять. | 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 |