Наши слоны Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт На столе лежит шахматная доска, в которой n строк и т столбцов. Слон может ходить по диагонали на…
Наши слоны Ограничение по времени: 1 секунда Ограничение по памяти: 256 мегабайт На столе лежит шахматная доска, в которой n строк и т столбцов. Слон может ходить по диагонали на любое количество клеток. Пустая клетка находится «под боем», если какой-либо из слонов на доске может одним ходом перейти на эту клетку. На доске в четырёх углах стоят четыре слона. Сколько клеток находится «под боем»? Формат входных данных В первой строке содержится количество строк шахматной доски п, во второй — столбцов m (2 ≤n, m ≤ 108). Формат выходных данных В единственной строке выведите целое число — количество клеток, находящихся «под боем». Система оценки Решения, правильно работающие при п, т ≤ 500, будут оцениваться в 52 балла.
Привет! Давай разберём твою задачу.
У нас есть шахматная доска с четырьмя слонами, стоящими в углах. Слоны могут ходить по диагонали на любое количество клеток. Нам нужно посчитать, сколько клеток на доске находится "под боем", то есть на которые может попасть слон одним ходом.
Начнем с углов:
- Верхний левый слон: Он может по диагонали двигаться вниз и вправо.
- Верхний правый слон: Он может по диагонали двигаться вниз и влево.
- Нижний левый слон: Он может по диагонали двигаться вверх и вправо.
- Нижний правый слон: Он может по диагонали двигаться вверх и влево.
Для каждой диагонали, слоны "обстреливают" две линии: главную и побочную диагонали. Чтобы посчитать уникальные клетки под боем, важно не считать одну клетку несколько раз.
Теперь решение:
- Слон "атакует" все клетки по диагоналям от своего угла.
- Посчитайте количество уникальных клеток на каждой диагонали, начиная с одной из углов, и расширяясь до противоположных углов.
Таким образом, итоговое количество клеток под боем будет равно: \[ (n - 1) + (m - 1) + (n - 1) + (m - 1) \] \[ = 2 \cdot (n + m) - 4 \]
Это связано с тем, что каждая диагональ идёт через все строки или столбцы, кроме того ряда или столбца, где стоит сам слон.
Теперь пример:
- Вход: 4 4
- Выход: 12
Это количество клеток, которые будут под боем у четырёх слонов на поле 4x4.
