Вопрос задан 04.09.2026 в 04:06. Предмет Информатика. Спрашивает Черноскутова Злата.

Спираль

Ограничение по времени: 1 секунда

В левом верхнем углу прямоугольного поля размера N×M сидит Черепашка. Она хочет закрасить некоторые клетки по спирали, закручивающейся к центру, как на рисунке:

Определите, сколько клеток ей придётся закрасить.

Формат входных данных
Первая строка входных данных содержит число N — высоту прямоугольника.
Вторая строка содержит число M — ширину прямоугольника.
Все числа целые положительные и не превосходят 2×10⁹.

Формат выходных данных
Программа должна вывести одно целое число — количество клеток, закрашенных Черепашкой.

Обратите внимание, что ответ в этой задаче может превышать возможное значение 32-битной целочисленной переменной, поэтому необходимо использовать 64-битные целочисленные типы данных (тип int64 в языке Pascal, тип long long в C++, тип long в Java и C#).

Система оценки
Решения, правильно работающие, когда числа N и M не превосходят 100, будут оцениваться в 40 баллов.
Решения, правильно работающие, когда числа N и M не превосходят 10⁵, будут оцениваться в 60 баллов.

Ввод: 5 6 5 1
Вывод: 20 5

Перейти к ответам

Отвечу на вопрос мгновенно! Нейросеть ChatGPT. Жми!

Ответы на вопрос

Отвечает Кириллова Катя.

В этой задаче нужно считать не все клетки прямоугольника, а клетки, которые попадают на линию спирали.

Удобно рассматривать спираль слоями. В каждом полном слое закрашивается верхняя строка, правая сторона, нижняя строка и часть левой стороны. Затем размеры внутреннего прямоугольника уменьшаются на \(4\) по высоте и на \(4\) по ширине, потому что между витками спирали остаётся промежуток.

Для больших \(N\) и \(M\) нельзя рисовать поле по клеткам: числа могут быть до \(2 \cdot 10^9\). Нужно вывести формулу или считать слоями, но так, чтобы количество шагов было маленьким.

Для примеров:

\[N=5,\ M=6\]

Количество закрашенных клеток равно \(20\).

\[N=5,\ M=1\]

Спираль превращается в один вертикальный столбец, поэтому закрашено \(5\) клеток.

В программе обязательно используйте 64-битный целый тип: в C++ это long long, потому что ответ может быть больше \(2^{31}-1\).