Matchstick Grid Rectangles
National Olympiad — Regional round (2016 season)
Submission name: rect.cpp
Problem summary
Build a complete rectangular grid of unit squares using exactly N matchsticks, including all internal grid edges. Count possible positive integer side lengths. Rotating a rectangle does not make a new one, and squares count.
Input
N, the number of matchsticks.
Output
The number of distinct grid rectangles, or 0 if none exist.
Constraints
1 ≤ N ≤ 1,000,000.
Worked example
An independently prepared example for this explanation.
Input
22
Output
2
Solution analysis
- A grid a squares wide and b squares high uses a(b + 1) horizontal edges and b(a + 1) vertical edges. Thus N = 2ab + a + b.
- Enumerate the smaller side a, enforcing a ≤ b. Rearranging gives b = (N − a) / (2a + 1). Count a precisely when the division is exact and b ≥ a. Stop when the square a-by-a already needs more than N sticks.
- For N = 22, a = 1 gives b = 21 / 3 = 7, and a = 2 gives b = 20 / 5 = 4. The next square needs 24 sticks, so the only two rectangles are 1-by-7 and 2-by-4.
Why it works
The edge-count formula counts every unit edge exactly once. For each smaller side a, the rearranged equation yields the only possible larger side b, accepted exactly when integral and at least a. Every rectangle has one such smaller side, so all valid rectangles are counted once and rotations are not duplicated.
Watch out. This counts all internal grid edges, not just the perimeter. Require positive sides and avoid double-counting rotations.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long n;
cin >> n;
int count = 0;
for (long long a = 1; 2 * a * a + 2 * a <= n; ++a) {
// N = 2ab + a + b determines b once the smaller side a is fixed.
long long numerator = n - a;
long long denominator = 2 * a + 1;
if (numerator % denominator == 0 && numerator / denominator >= a) {
++count;
}
}
cout << count << '\n';
return 0;
}