Question

Спираль

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


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


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


Формат входных данных

Первая строка входных данных содержит число N — высоту прямоугольника.

Вторая строка содержит число M — ширину прямоугольника.

Все числа целые положительные и не превосходят 2×109.


Формат выходных данных

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

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


Система оценки

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

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


Ввод 5 6 5 1

Вывод 20 5

Answer 1

Python:

n, m = [int(input()) for h in range(2)]

ans = 0

while n >= 4 and m >= 4:

   k = min(n, m) // 4

   ans += ((n + m) + (n + m) - 4 * (k - 1)) * k // 2

   n, m = n - 2 * k, m - 2 * k

if n == 3 and m >= 3:

   ans += 2 * m + 1

elif n == 2 and m >= 2:

   ans += m + 1 + int(m >= 3)

elif m == 3 and n >= 3:

   ans += 2 * n + 1

elif m == 2 and n >= 2:

   ans += n + 1

else:

   ans += n * m

print(ans)