Turns in a Spiral
National Olympiad — National round (2018 season)
Submission name: spiral.cpp
Problem summary
A robot starts in the top-left cell of an N-row, M-column rectangle facing right. It visits all cells in a clockwise inward spiral and stops immediately after the last cell. Count its direction changes, including an initial turn if a nontrivial single-column rectangle forces it to move downward.
Input
Two integers N and M.
Output
The number of direction changes.
Constraints
1 ≤ N, M ≤ 4000000000.
Worked example
An independently prepared example for this explanation.
Input
3 5
Output
4
Solution analysis
- A cell-by-cell simulation is impossible at these sizes. Only the shorter dimension matters for how many layers the spiral can peel away. Each complete outer layer contributes four turns and reduces both dimensions by two.
- The resulting formula is 2·N−2 when N ≤ M, and 2·M−1 when N > M. For a wide or square rectangle, the final remaining strip is reached after an even number of turns; a taller rectangle needs one additional downward turn.
- For 3 by 5, the robot goes right, down, left, up, then right across the center: four direction changes. A 1 by M row needs zero turns; an N by 1 column with N>1 needs one initial turn from right to down. A single cell needs none.
Why it works
For N,M ≥ 3, traversing the perimeter reaches the inner rectangle with four direction changes, so T(N,M)=4+T(N−2,M−2). For a one-row rectangle T=0; for a one-column rectangle with more than one cell T=1. With two rows and at least two columns T=2, and with two columns and more than two rows T=3. The stated formula matches these bases and increases by four when both dimensions increase by two, so it satisfies the recurrence.
Watch out. The robot does not turn after finishing. Use 64-bit integers: both dimensions and the turn count can exceed signed 32-bit limits.
Commented C++17 solution
An independently written complete program with standard headers.
#include <algorithm>
#include <array>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>
using namespace std;
int main() {
long long rows, columns;
cin >> rows >> columns;
long long turns;
// A taller rectangle requires one extra downward turn in its final strip.
if (rows <= columns) {
turns = 2 * rows - 2;
} else {
turns = 2 * columns - 1;
}
cout << turns << '\n';
}