|
3 тур - з 20.11 по 26.11.2017
точка входу для відправлення розв’язків
http://134.249.159.199/cgi-bin/new-client?contest_id=45
(скачати)
ЗАДАЧА 1. Слон (20 балів)
Ім’я вхідного файлу: input.txt
Ім’я вхідного файлу: output.txt
Ліміт часу: 1с.
Є шахова дошка NxN клітинок. На дошку встановили M шахових слонів. Як відомо, така шахова фігура «б’є» клітинки поля по діагоналі. Будемо називати ті клітинки, які не під боєм хоча б одним слоном, безпечними. Потрібно порахувати кількість таких безпечних клітинок
Вхідні дані
В єдиному рядку вхідного файлу вказано натуральне число N (1 ≤ N ≤ 1000 000) і М (1 ≤ M ≤ 10000), а далі M пар чисел від 1 до N включно – номер рядка і номер стовпця дошки, на перетині яких знаходиться відповідний слон. Нумерація рядків і стовпців розпочинається з одиниці. Ніякі 2 слони не стоять в одній клітинці.
Вихідні дані
У вихідний файл виведіть єдине число – кількість безпечних клітинок.
Приклад,
|
Вхідні дані
|
Вихідні дані
|
|
10 6 4 7 8 5 8 7 6 2 9 7 8 4
|
33
|
ЗАДАЧА 2. Магараджа (100 балів)
Ім’я вхідного файлу: input.txt
Ім’я вхідного файлу: output.txt
Ліміт часу: 5с.
Магараджа це фігура, яка може ходити як ферзь або як кінь в шахах. Ваше завдання - знайти кількість способів якими на шахівниці NxN можна було розставити N магараджі так, щоб вони не били один одного.
Вхідні дані
В єдиному рядку вхідного файлу вказано N (N (1 ≤ N ≤ 50) розмір дошки.
Вихідні дані
У вихідний файл виведіть єдине число K, кількість способів розміщення магараджі.
Приклад,
|
Вхідні дані
|
Вихідні дані
|
|
10
|
4
|
|
