ГлавнаяСборникиТурнирыРазделыФорумыУчастникиПечатьПомощьО системе

Турниры > Городская олимпиада школьников 2011 (9-11 классы) > задача:


6. Операционные системы

Городская олимпиада школьников 2011 (9-11 классы)

Старт: 25.ноя.2011 в 11:13:11
Финиш: 31.мая.2012 в 23:59:59
Турнир завершён!
• Турнирная таблица

Задачи турнира

• 1. Победитель олимпиады
• 2. Кодовый замок
• 3. Покупка грибов
• 4. Расстановка ноутбуков
• 5. Сообщение
• 6. Операционные системы

Обратная связь

Если у вас есть предложения или пожелания по работе Contester, посетите форум сайта www.contester.ru.

Лимит времени 2000/4000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.

Васин жесткий диск состоит из M секторов. Вася последовательно устанавливал на него различные операционные системы следующим методом: он создавал новый раздел диска из последовательных секторов, начиная с сектора номер ai и до сектора bi включительно, и устанавливал на него очередную систему. При этом если очередной раздел хотя бы по одному сектору пересекается с каким-то ранее созданным разделом, то ранее созданный раздел «затирается», и операционная система, которая на него была установлена, больше не может быть загружена.
Напишите программу, которая по информации о том, какие разделы на диске создавал Вася, определит, сколько в итоге работающих операционных систем установлено и в настоящий момент работает на Васином компьютере.

Формат входного файла
Сначала вводятся натуральное число M — количество секторов на жестком диске (1 ≤ M ≤ 109) и целое число N — количество разделов, которое последовательно создавал Вася (0 ≤ N ≤ 1000).
Далее идут N пар чисел ai и bi, задающих номера начального и конечного секторов раздела (1 ≤ ai ≤ bi ≤ M).

Формат выходного файла
Выведите одно число — количество работающих операционных систем на Васином компьютере.

Примеры
Вход
10
3
1 3
4 7
3 4
Выход
1

Вход
10
4
1 3
4 5
7 8
4 6
Выход
3

Для отправки решений необходимо выполнить вход.

www.contester.ru