Number in the Expanding Square
National Olympiad — National round (2022 season)
Submission name: table.cpp
Problem summary
An infinite table begins with 1 at row 1, column 1. The next square layer is filled down its right column and left along its bottom row; the following layer is filled right along its bottom row and up its right column. These two directions alternate. The first rows begin [1,2,9,10], [4,3,8,11], [5,6,7,12], [16,15,14,13]. Find the row and column containing N.
Input
One integer N.
Output
The one-based row and column.
Constraints
1 ≤ N ≤ 10,000.
Worked example
An independently prepared example for this explanation.
Input
15
Output
4 2
Solution analysis
- Find the smallest side length S such that S² ≥ N. The new layer contains numbers (S−1)²+1 through S² and lies on row S or column S.
- Let offset = N−(S−1)²−1. For even S, start at (1,S), move down for S cells, then left along the bottom row. For odd S, start at (S,1), move right, then up.
- For N=15, S=4 and offset=5. The even layer visits 10,11,12,13 down column 4, then 14 at (4,3), 15 at (4,2), and 16 at (4,1). Thus output 4 2.
Why it works
The completed square of side S−1 contains exactly (S−1)² entries. The remaining 2S−1 cells of the next layer form the stated two-edge path. The parity-based offset formulas give each cell of that path in precisely the diagram’s alternating order.
Watch out. Coordinates are row then column, both one-based. The corner belongs to both edges but is counted only once. Layer direction alternates with parity.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int side = 1;
while (side * side < n) {
side++;
}
// Remove the completed inner square and use a zero-based layer offset.
int offset = n - (side - 1) * (side - 1) - 1;
int row, column;
if (side % 2 == 0) {
if (offset < side) {
row = offset + 1;
column = side;
} else {
row = side;
column = 2 * side - offset - 1;
}
} else {
if (offset < side) {
row = side;
column = offset + 1;
} else {
row = 2 * side - offset - 1;
column = side;
}
}
cout << row << ' ' << column << '\n';
}