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