Задача Mayor2
Вже відомий нам мер Балдуйська вирішив зменшити витрати на
організацію автобусних маршрутів. Саме місто мало
N вулиць, що розміщені строго з півдня на північ, і
N вулиць, що їх перетинають і розташовані із заходу на схід. Всі вулиці,
природно, однакової довжини з одностороннім рухом (тобто
їхати можна або з півдня на північ, або із заходу на схід).
Вранці на деяких перехрестях збираються люди. Їх забирають
автобуси "безрозмірної" місткості, щоб відвезти на
роботу за місто. Та ось одна маленька проблема: всі автобуси
починають свій маршрут з самого південно-західного
перехрестя. Яку мінімальну кількість автобусів слід
випускати на маршрут вранці, щоб підібрати всіх пасажирів,
що стоять на перехрестях?
Технічні умови: Програма зчитує з клавіатури два натуральні
числа :N – кількість вулиць у кожному напрямку
(N<=1000), P – кількість перехресть із пасажирами
(1<P<=1000000), а далі P груп по 2 числа – координати перехрестя з
пасажирами. Зрозуміло, що "саме південно-західне"
перехрестя має координаті (1,1). Всі числа вводяться одним рядком через
пропуски. Програма виводить на екран одне число – шукану
величину.
Приклад
Введення 8 8 3 1 4 2 7 3 2 4 5 4 3 6 4 7 7 6
Виведення 3
Задача Mayor2
Уже известный нам мэр Балдуйска решил уменьшить расходы на организацию автобусных маршрутов. Сам город имел
N улиц, идущих строго с юга на север, и
N пересекающих их улиц, идущих с запада на восток. Все улицы, естественно, одинаковой длины, а движение по ним одностороннее (т.е. ехать можно либо с юга на север, либо с запада на восток). Утром на некоторых перекрестках собираются люди. Их подбирают безразмерные автобусы, дабы отвезти на работу за город. Да вот одна маленькая проблема: все автобусы начинают свой маршрут с самого юго-западного перекрестка, Какое минимальное количество автобусов следует выпускать на маршрут утром, чтобы подобрать всех стоящих на перекрестках пассажиров?
Технические условия: Программа читает с клавиатуры два натуральных числа:
N – количество улиц в каждом направлении (N<=1000),
P – количество перекрестков с стоящими пассажирами (1<P<=1000000), а далее P групп по
2 числа – координаты перекрестка с пассажирами.
Понятно, что "самый юго-западный
перекресток имеет координаты (1,1) Все числа вводятся одной строкой через пробелы.
Прoграмма выводит на экран единственное число
– искомую величину.
Пример:
Ввод 8 8 3 1 4 2 7 3 2 4 5 4 3 6 4 7 7 6
Вывод 3