Великая шахматная партия (emperor)
Главный противник Гарри Поттера лорд Волан-де-Морт, которого многие считали погибшим, тайно возвращается в Хогвардс. Для этого он использует тело профессора защиты от темных искусств Квиреуса Квиррелла. С его помощью он принимается искать философский камень, думая восстановить тело Темного лорда. Гарри Поттер активно ему противодействует и его друзья – Рон Уизли и Гермиона Грейнджер – помогают ему в борьбе. В один из самых критических моментов Рону предлагается сыграть в волшебные шахматы по новым правилам. На шахматном поле кроме обычных фигур находится новая фигура – так называемый Император.
- На своем первом ходу Император сбивает любую шахматную фигуру, которая стоит на одной с ним горизонтали или вертикали и переходит на ее место.
- На любом следующем ходу Император сбивает любую шахматную фигуру на той же вертикали (если предыдущий ход этого Императора был по горизонтали) или горизонтали (если предыдущий ход был по вертикали) и переходит на ее место.
- Император не может сделать ход если он не может сбить вражескую фигуру.
Известно положение шахматных фигур на доске. Рону необходимо срочно рассчитать, какое наименьшее количество Императоров нужно поставить на доску так, чтобы они могли сбить все шахматные фигуры. При этом Императоры могут делать любое количество ходов, а шахматные фигуры не движутся. Размер доски: 108×108.
Формат ввода-вывода:
Программа emperor читает с клавиатуры (стандартного устройства ввода) целое число N (1 <= N <= 105) – количество шахматных фигур. Затем считывается N пар целых чисел (в диапазоне от 1 до 108), позиции шахматных фигур.
Программа emperor выводит на экран (стандартное устройства вывода) единственное число – наименьшее количество Императоров для полной победы.
Пример входных и выходных данных:
|
Ввод |
Вывод |
|
4 1 1 1 2 1 3 1 4 |
2 |