В левом верхнем углу прямоугольного поля размера 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
20
1
5
5
n = int(input()) //вводим n
m = int(input()) //водим m
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) // выводим ответ
