Решение на 40 баллов создаёт двумерный массив размером $$$N\times M$$$ и моделирует движение черепашки, отмечая в массиве закрашенные клетки. Такое решение довольно трудно в реализации, приведем пример реализации на языке C++. Решение имеет сложность $$$O(NM)$$$.
[language=C++, frame=single]
#include<iostream>
#include<vector>
using namespace std;
int n, m;
vector <vector<bool>> used;;
unsigned int ans = 0;
int di[4] = {1, 0, -1, 0};
int dj[4] = {0, 1, 0, -1};
bool check_used(int i, int j)
{
return i >= 0 && i < n && j >= 0 && j < m && used[i][j];
}
bool check_good(int i, int j)
{
if (i < 0 || i >= n || j < 0 || j >= m)
return false;
int count = check_used(i - 1, j) + check_used(i + 1, j)
+ check_used(i, j - 1) + check_used(i, j + 1);
return count == 1;
}
int main()
{
cin >> n >> m;
used.resize(n, vector<bool>(m));
int i = 0;
int j = 0;
int dir = 0;
while (true)
{
++ans;
used[i][j] = true;
int i1 = i + di[dir];
int j1 = j + dj[dir];
if (check_good(i1, j1))
{
i = i1;
j = j1;
continue;
}
dir = (dir + 1) % 4;
i = i + di[dir];
j = j + dj[dir];
if (!check_good(i, j))
break;
}
cout << ans << endl;
}
Чтобы написать решение на 60 баллов, рассмотрим движение черепашки вдоль левой стороны прямоугольника. Черепашка закрасит столбец из $$$N$$$ клеток. Теперь пусть черепашка сдвинется на одну клетку вправо, закрасив суммарно $$$N+1$$$ клетку. Справа от черепашки теперь располагается прямоугольник из $$$M-2$$$ столбцов и $$$N$$$ строк, и черепашка начинает обходить его вдоль стороны длиной $$$M - 2$$$. То есть мы свели задачу от прямоугольника размером $$$N\times M$$$ к прямоугольнику размером $$$(M-2)\times N$$$, закрасив $$$N+1$$$ клетку. Это можно сделать, если $$$N\ge 2$$$ и $$$M\ge 2$$$. Пока соблюдается это условие, будем в цикле прибавлять к ответу $$$N + 1$$$ и менять числа $$$(N, M)$$$ на $$$(M - 2, N)$$$.
В результате мы получим либо вырожденный пустой прямоугольник (если мы отрежем от него всё), либо прямоугольник, одна из сторон которого равна 1. В этом случае черепашка закрасит весь оставшийся прямоугольник, в котором будет $$$MN$$$ клеток.
Такое решение имеет сложность $$$O(M + N)$$$ и набирает 60 баллов. Пример решения на языке Python.
[language=Python, frame=single]
n = int(input())
m = int(input())
ans = 0
while n >= 2 and m >= 2:
ans += n + 1
n, m = m - 2, n
ans += m * n
print(ans)
Наконец, для решения на полный балл заметим, что суммируются числа вида $$$N + 1$$$, $$$M-2+1$$$, $$$N-2+1$$$, $$$M-4+1$$$, $$$N - 4 + 1$$$, ... То есть каждое следующее горизонтальное или вертикальное перемещение черепашки окажется на 2 короче предыдущего горизонтального или вертикального перемещения, и мы суммируем арифметические прогрессии, что можно сделать без использования цикла.
Удобней суммировать не две прогрессии, а одну. Рассмотрим передвижения черепашки вдоль сторон прямоугольника: вниз на $$$N$$$ клеток, вправо на $$$M-1$$$ клеток, затем вверх на 1 клетку. Так мы перейдём к прямоугольнику размером $$$(N - 2) \times (M - 2)$$$, прибавив к ответу $$$N + M$$$. На следующем шаге мы поибавим к ответу $$$(N - 2) + (M - 2)$$$, затем опять уменьшим стороны прямоугольника на 2. Мы получим арифметическую прогрессию с начальным членом $$$N+M$$$ и разностью $$$-4$$$.
Посчитаем количество членов этой прогрессии — число возможных сокращений сторон прямоугольника на 2, пока не останется прямоугольник, наименьшая сторона которого будет не более 2. Обозначим это число за $$$k$$$. Добавим к ответу сумму арифметической прогрессии из $$$k$$$ членов c начальным значением $$$n+m$$$ и разностью $$$-4$$$, и разберём случаи разного количества закрашенных клеток в оставшемся прямоугольнике.
Такое решение имеет сложность $$$O(1)$$$, пример решения на языке Python.
[language=Python, frame=single]
n = int(input())
m = int(input())
k = min(n - 1, m - 1) // 2
ans = ((n + m) + (n + m) - 4 * (k - 1)) * k // 2
n -= 2 * k
m -= 2 * k
if n == 1:
ans += m
elif m == 1:
ans += n
elif m == 2:
ans += n + 1
else: # n == 2, m > 2
ans += m + 2
print(ans)