Two Zigzag Walks
National Olympiad — Municipal round
Submission name: zigzag.cpp
Problem summary
Two tokens start at (1,1) on an m-row, n-column board and move simultaneously one cell per step. One follows rows in alternating horizontal directions, stepping down at each row end; the other follows columns in alternating vertical directions, stepping right at each column end. Count cells occupied by both at the same time, excluding the starting cell.
Input
m n.
Output
The number of meetings after the start.
Constraints
2 < m,n < 300.
Worked example
An independently prepared example for this explanation.
Input
4 4
Output
3
Solution analysis
- Number steps from zero. The horizontal walker is in row t/n, with column t%n or its reflection depending on row parity.
- The vertical walker is in column t/m, with analogous row reflection.
- Compare coordinates for every t from 1 to mn−1.
Why it works
The formulas describe exactly the two serpentine traversals, each visiting one new cell per step. Equal coordinates are precisely meetings.
Watch out. Do not count merely visiting the same cell at different times.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: The formulas describe exactly the two serpentine traversals, each visiting one new cell
// per step. Equal coordinates are precisely meetings.
#include<iostream>
using namespace std;
int main(){
int m,n;
cin>>m>>n;
int ans=0;
for(int t=1;t<m*n;t++){
int r=t/n,c=t%n;
if(r%2){
c=n-1-c;
}
int y=t/m,x=t%m;
if(y%2){
x=m-1-x;
}
ans+=r==x&&c==y;
}
cout<<ans<<'\n';
}