Summing One Spiral Row
National Olympiad — Municipal round (2023 season)
Submission name: spiral.cpp
Problem summary
Consecutive integers starting at M fill an N×N clockwise spiral from the top-left, initially rightwards. Sum row P from the top.
Input
M N P.
Output
The row sum.
Constraints
1≤N≤1000; 1≤M<10^6; 1≤P≤N.
Worked example
Input and output for the worked example discussed below.
Input
10 6 4
Output
209
Solution analysis
- For zero-based cell(r,c), layer=min(r,c,N−1−r,N−1−c). Its layer’s remaining side length is s=N−2layer, with N²−s² cells filled earlier.
- The layer begins at M+N²−s². Add the offset on its top, right, bottom or left side following clockwise order; ordered side tests avoid double-counting corners.
- Evaluate each column in the chosen row without constructing the whole square. The sample row contains27,40,45,44,35,18, whose sum is209.
Why it works
The difference of square areas counts all preceding layers. Each side-offset formula follows the spiral traversal within its layer, giving the exact cell value. Summing those values gives the requested row.
Complexity: O(N) time and O(1) auxiliary space.
Watch out. Rows start from the top; handle a side-one centre and corners. Use long long for the row sum.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<algorithm>
using namespace std;
// The difference of square areas counts all preceding layers.
int main(){
long long first;
int n,row;
cin>>first>>n>>row;
row--;
long long answer=0;
for(int col=0;col<n;col++){
int layer=min(min(row,col),min(n-1-row,n-1-col));
int side=n-2*layer,far=n-layer-1;
long long offset;
if(row==layer){
offset=col-layer;
}
else if(col==far){
offset=side-1+row-layer;
}
else if(row==far){
offset=2LL*(side-1)+far-col;
}
else{
offset=3LL*(side-1)+far-row;
}
answer+=first+1LL*n*n-1LL*side*side+offset;
}
cout<<answer<<'\n';
}