Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт На столе лежит шахматная доска, в которой п строк и т столбцов. Слон может ходить по диагонали на любое…
Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт На столе лежит шахматная доска, в которой п строк и т столбцов. Слон может ходить по диагонали на любое количество клеток. Пустая клетка находится «под боем», если какой-либо из слонов на доске может одним ходом перейти на эту клетку. На доске в четырёх углах стоят четыре слона. Сколько клеток находится «под боем»? Формат входных данных В первой строке содержится количество строк шахматной доски п, во второй - столбцов т (2 _ n, m _ 108). Формат выходных данных В единственной строке выведите целое число - количество клеток, находящихся «под боем». Система оценки Решения, правильно работающие при п, т 500, будут оцениваться в 52 балла. Замечание
Для решения этой задачи, давайте сначала определим, какие клетки находятся под боем слонов, расположенных в углах шахматной доски.
Позиции слонов:
- Первый слон находится в координатах (1, 1) — верхний левый угол.
- Второй слон в (1, m) — верхний правый угол.
- Третий слон в (n, 1) — нижний левый угол.
- Четвёртый слон в (n, m) — нижний правый угол.
Ход слона: Слон движется по диагоналям, и, соответственно, он может угрожать клеткам, находящимся на тех же диагоналях, что и он сам. Рассмотрим, как это происходит:
- Слон в (1, 1) угрожает всем клеткам, где разность индексов строки и столбца равна 0 (main diagonal) и суммы индексов строки и столбца равна постоянной (anti diagonal).
- Слон в (1, m) будет угрожать клеткам по диагонали, где i + j = m + 1 и i - j = 1 - m.
- Слон в (n, 1) угрожает клеткам, где i + j = n + 1 и i - j = n - 1.
- Слон в (n, m) охватывает клетки, где i + j = n + m и i - j = n - m.
Вычисление клеток под боем:
- Считаем все клетки, находящиеся под боем от каждого из слонов, но при этом учитываем, что клетки могут пересекаться.
- Каждая диагональ содержит определённое количество клеток, которые слоны могут атаковать.
На практике, такое количество клеток может быть подсчитано следующим образом:
- Слон (1, 1) атакует клетки: (1, 2), (2, 1), (2, 2), … до (n, m).
- Слон (1, m) атакует аналогично, меняются только координаты.
- То же самое для остальных слонов.
После учёта всех клеток с уникальными координатами, получаем общее количество клеток, находящихся под боем. Необходимо также учесть, что углы (1,1), (1,m), (n,1) и (n,m) не должны считаться дважды.
Для примера, общее количество уникальных клеток, находящихся под боем слонов на доске (n, m):
- В результате, общее количество клеток будет равно примерно \( (n - 1) + (m - 1) + (n - 1) + (m - 1) \).
Таким образом, количество клеток под боем будет: \[ \text{Количество клеток под боем } = 2 \times (n + m - 2) \]
Эта формула работает при \( n \geq 2 \) и \( m \geq 2 \). Теперь вы можете использовать эту логику для вычисления количества клеток, находящихся «под боем» слонов.
