Завдання 3 туру 2017 |
Написав Гісь Ігор Володимирович | ||||||||
Четвер, 16 листопада 2017, 22:29 | ||||||||
3 тур - з 20.11 по 26.11.2017 точка входу для відправлення розв’язків (скачати)
ЗАДАЧА 1. Слон (20 балів) Ім’я вхідного файлу: input.txt Ім’я вхідного файлу: output.txt Ліміт часу: 1с. Є шахова дошка NxN клітинок. На дошку встановили M шахових слонів. Як відомо, така шахова фігура «б’є» клітинки поля по діагоналі. Будемо називати ті клітинки, які не під боєм хоча б одним слоном, безпечними. Потрібно порахувати кількість таких безпечних клітинок Вхідні дані В єдиному рядку вхідного файлу вказано натуральне число N (1 ≤ N ≤ 1000 000) і М (1 ≤ M ≤ 10000), а далі M пар чисел від 1 до N включно – номер рядка і номер стовпця дошки, на перетині яких знаходиться відповідний слон. Нумерація рядків і стовпців розпочинається з одиниці. Ніякі 2 слони не стоять в одній клітинці. Вихідні дані У вихідний файл виведіть єдине число – кількість безпечних клітинок. Приклад,
ЗАДАЧА 2. Магараджа (100 балів) Ім’я вхідного файлу: input.txt Ім’я вхідного файлу: output.txt Ліміт часу: 5с.
Магараджа це фігура, яка може ходити як ферзь або як кінь в шахах. Ваше завдання - знайти кількість способів якими на шахівниці NxN можна було розставити N магараджі так, щоб вони не били один одного.
Вхідні дані В єдиному рядку вхідного файлу вказано N (N (1 ≤ N ≤ 50) розмір дошки. Вихідні дані У вихідний файл виведіть єдине число K, кількість способів розміщення магараджі. Приклад,
|