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

На шахматной доске размером 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 ≤ N²). В каждой из следующих K строк записаны целые числа y и x - номера строки и столбца доски, где стоит слон (1 ≤ x, y ≤ N). Никакие два слона не стоят в одной и той же клетке.

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

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

Пример

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

Здесь определена стандартная шахматная доска 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).

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

[Обсуждение] [Все попытки] [Лучшие попытки]