`Всеукраїнський центр проведення олімпіад в мережі Інтернет
Задача NewArea

Задача 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

© LIKT 1998-2024