Letters in Repeated Zigzag Rows
National Olympiad — National round (2020 season)
Submission name: zigzag.cpp
Problem summary
Write a lowercase string repeatedly down and up N zigzag rows. Read each row left to right and answer the letter at a given position in it.
Input
N, string S, T, then T row/position pairs.
Output
One queried letter per line.
Constraints
2 ≤ N ≤ 1000; 1 ≤ |S| ≤ 100000; 2 ≤ T ≤ 100000; positions 1…10^9.
Worked example
Input and output for the worked example discussed below.
Input
3 hubavden 3 1 2 2 3 3 4
Output
v d e
Solution analysis
- The motion repeats after P=2(N−1) steps. A 0-based boundary row r occurs once per period at offset r; an interior row occurs twice, at offsets r and P−r.
- Boundary position B maps to global index r+(B−1)P. An interior row uses block floor((B−1)/2), with offset r for odd B and P−r for even B.
- The repeated source character is S[index modulo |S|]. In the sample row 2 receives global indices 1,3,5,…, so its third letter is S[5]=d.
Why it works
Periodic row offsets enumerate exactly the source-stream positions assigned to each row.
Complexity: O(|S|+T) time and O(|S|) space, with O(1) arithmetic per query.
Watch out. Use 64-bit global indices; top and bottom rows have only one offset each. Query positions are 1-based.
Commented C++17 solution
An independently written complete program with standard headers.
// Periodic row offsets enumerate exactly the source-stream positions assigned to each row.
#include<iostream>
#include<string>
using namespace std;
int main(){
int rows;
string text;
cin>>rows>>text;
int queries;
cin>>queries;
long long period=2LL*(rows-1);
while(queries--){
int row;
long long position;
cin>>row>>position;
row--;
long long index;
if(row==0||row==rows-1){
index=row+(position-1)*period;
}
else{
index=(position-1)/2*period+(position%2==1?row:period-row);
}
cout<<text[index%text.size()]<<'\n';
}
}