Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки

HotLog


 

Слоны на шахматной доске

(Время: 1 сек. Память: 16 Мб Сложность: 33%)
Слоны на шахматной доске

На шахматной доске размером N×N находится K слонов. Слон - это шахматная фигура, которая может ходить по любой из диагоналей на любое количество клеток по свободным (пустым) клеткам. Сквозь другие фигуры слон ходить не может. На рисунке справа показаны все пустые клетки (они подсвечены зелёным цветом), которые бьёт слон E6 (он подсвечен красным цветом), т.е. в эти 8 клеток этот слон может перемещаться (ходить). В клетку A2 слон E6 не может переместиться, т.к. на его пути стоит слон B3.

В этой задаче необходимо вычислить следующее:

  1. количество пустых клеток, которые бьются хотя бы одним слоном;
  2. наибольшее количество слонов, которые бьют одну и ту же пустую клетку;
  3. количество пустых клеток, которые бьются наибольшим количеством слонов;
  4. количество слонов, которые находятся на главной диагонали (x=y);
  5. количество слонов, которые находятся на побочной диагонали (x=n-y+1).

Входные данные

Первая строка входного файла INPUT.TXT содержит целые числа N и K - размер шахматной доски и количество слонов (1 ≤ N ≤ 100, 1 ≤ K ≤ N2). В каждой из следующих K строк записаны целые числа y и x - номера строки и столбца доски, где стоит слон (1 ≤ x, y ≤ N). Никакие два слона не стоят в одной и той же клетке.

Выходные данные

В выходной файл OUTPUT.TXT выведите пять чисел через пробел - параметры, перечисленные в условии задачи.

Пример

INPUT.TXTOUTPUT.TXT
8 5
6 5
3 2
3 8
6 2
4 5
32 3 2 0 1

Пояснение к примеру

Здесь определена стандартная шахматная доска 8×8 (N=8), изображенная на рисунке выше. Во входных данных идет перечисление координат пяти слонов (K=5): E6, B3, H3, B6 и E4. Ответ содержит следующие пять чисел:

  1. 32 - именно столько пустых клеток суммарно бьются всеми слонами;
  2. 3 - столько слонов бьют каждую из клеток D5 и F5 (D5 бьётся слонами B3, E4 и E6; F5 бьётся слонами H3, E4 и E6), и это максимальное значение, т.к. никакая другая пустая клетка не бьётся четырьмя и более слонами одновременно;
  3. 2 - количество пустых клеток, которые бьются наибольшим количеством слонов, как было сказано выше, это клетки D5 и F5 - их ровно две;
  4. 0 - количество слонов, которые находятся на главной диагонали (на главной диагонали нет слонов);
  5. 1 - количество слонов, которые находятся на побочной диагонали (на побочной диагонали стоит только один слон E4).

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Личные олимпиады
 Командные олимпиады
 Первая личная олимпиада
 Вторая личная олимпиада
 Третья личная олимпиада
 Четвертая личная олимпиада
 Пятая личная олимпиада
 Шестая личная олимпиада
 Седьмая личная олимпиада
 A. Три поросёнка
 B. Слоны на шахматной доске
 C. Взрывчатка
 D. Химические реакции

Красноярский краевой Дворец пионеров, (c)2006 - 2022, E-mail: admin@acmp.ru