Diagonal Cipher
National Olympiad — National round
Submission name: secret.cpp
Problem summary
The encoded string is an n×n square written row by row. Sum all decimal digit values and take the remainder modulo n to obtain starting row k (zero-based); begin at (k,0). Read uppercase letters along the encoding path: normally advance one row down and one column right. Crossing the bottom instead wraps to row zero in the SAME column; crossing the right edge wraps to column zero on the next row. Stop at the first non-uppercase character. Recover the nonempty message.
Input
One encoded string without whitespace.
Output
The decoded uppercase message.
Constraints
Encoded length is a square between 4 and 10^6 inclusive; symbols are uppercase Latin letters, digits and punctuation; at least one digit is present.
Worked example
An independently prepared example for this explanation.
Input
A!2B
Output
AB
Solution analysis
- Infer n from the string length and compute k from all digit values.
- Index a square cell (r,c) as r*n+c.
- Follow the exact boundary rules until a terminator is reached. The guaranteed encoding supplies a nonletter after the message.
Why it works
The decoder starts at the same cell and applies the encoding successor rule, so it reads the message in its original order.
Watch out. Bottom wrap retains the column; ordinary toroidal diagonal movement would be wrong.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: The decoder starts at the same cell and applies the encoding successor rule, so it reads
// the message in its original order.
#include<iostream>
#include<string>
#include<cmath>
using namespace std;
int main(){
string s;
cin>>s;
int n=sqrt(s.size()),sum=0;
for(char c:s){
if(c>='0'&&c<='9'){
sum+=c-'0';
}
}
int r=sum%n,c=0;
for(size_t steps=0;steps<s.size();steps++){
char ch=s[r*n+c];
if(ch<'A'||ch>'Z'){
break;
}
cout<<ch;
r++;
if(r==n){
r=0;
}
else{
c=(c+1)%n;
}
}
cout<<'\n';
}