Decode a Message Wrapped Around a Rod
National Olympiad — National round (2024 season)
Submission name: decoding.cpp
Problem summary
Decode a message wrapped with d symbols per turn around a rod. The encoded body concatenates rod rows cyclically from row s; nine-complement digits of d and s surround it.
Input
One complete encoded line, preserving spaces.
Output
The original message line.
Constraints
3≤d≤message length≤10000; 1≤s≤d. The original first and last d characters contain no digits.
Worked example
Input and output for the worked example discussed below.
Input
3an al ansaNlak Oa ovI fv !nioHE7
Output
Ela v Haskovo na finala na NOI!
Solution analysis
- The initial and final digit runs unambiguously encode d and s because of the nondigit boundary guarantee. Replace each digit by its complement to 9 and preserve every body space.
- Positions r,r+d,r+2d,… of the original form rod row r, but are copied backwards because wrapping starts at the right end. Rows appear cyclically in order s−1,s,…,d−1,0,… .
- For row r, its last original position is r+floor((n−1−r)/d)d. Place successive encoded characters there while subtracting d. The official boundary digits give d=6,s=2, restoring Ela v Haskovo na finala na NOI!.
Why it works
Each original position belongs to one residue class modulo d and has a unique reversed position in that row. Processing the rows in their encoded cyclic order therefore reverses the permutation exactly and fills every original position once.
Watch out. Use getline for spaces. Decode a multidigit suffix in forward order. Different rows may have different lengths.
Commented C++17 solution
An independently written complete program with standard headers.
#include<cctype>
#include<iostream>
#include<string>
using namespace std;
int main(){
string encoded;
getline(cin,encoded);
int left=0;
int rows=0;
while(isdigit(static_cast<unsigned char>(encoded[left]))){
rows=rows*10+9-(encoded[left]-'0');
left++;
}
int right=int(encoded.size());
while(isdigit(static_cast<unsigned char>(encoded[right-1]))){
right--;
}
int start=0;
for(int i=right;i<int(encoded.size());i++){
start=start*10+9-(encoded[i]-'0');
}
int length=right-left;
string answer(length,' ');
int cursor=left;
for(int offset=0;offset<rows;offset++){
int row=(start-1+offset)%rows;
int last=row+((length-1-row)/rows)*rows;
// Copied rows reverse positions with the same residue modulo rows.
for(int position=last;position>=0;position-=rows){
answer[position]=encoded[cursor++];
}
}
cout<<answer<<'\n';
}