Hidden Messages
National Olympiad — National round (2011 season)
Submission name: message.cpp
Problem summary
Given a substitution table, decode a message. Each table row contains a decoded character, one separating space, and its encoded character. A literal space may itself be either character, so preserve the exact row positions.
Input
N; then N three-character table rows decoded-space-encoded; then one full encoded message line.
Output
The decoded message, preserving all decoded spaces.
Constraints
Message length ≤ 80. Characters are uppercase Latin letters, digits, space, =, <, >, period, comma, and !.
Worked example
An independently prepared example for this explanation.
Input
15 A 5 B B C 4 D Q F I L J T K M 7 E Z N 8 5 > . X 9 E O Y 4Y7ZFL8
Output
COME IN
Solution analysis
- Read each mapping row with getline. The decoded symbol is row[0], the separator is row[1], and the encoded symbol is row[2]. Token extraction would skip meaningful spaces.
- Store a reverse lookup from encoded character to decoded character. Read the entire final message line and translate each character through that lookup.
- In the sample, 4 maps to C, Y to O, 7 to M, Z to E, F to a space, L to I, and 8 to N. Thus 4Y7ZFL8 becomes COME IN. The row for K maps an encoded space to K.
Why it works
For each table row the reverse lookup stores exactly the decoded character corresponding to its encoded character. Each message position is independently replaced using that lookup, so every output character is the correct decoding of the matching input position, including spaces.
Watch out. Do not trim rows or the message. Use getline rather than >> for character pairs; an encoded trailing space is data.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <string>
using namespace std;
int main() {
int n;
cin >> n;
string line;
getline(cin, line);
char decoded[256];
for (int i = 0; i < 256; i++) {
decoded[i] = static_cast<char>(i);
}
for (int i = 0; i < n; i++) {
getline(cin, line);
if (!line.empty() && line.back() == '\r') {
line.pop_back();
}
// Preserve literal spaces at either end of a mapping row.
if (line.size() < 3) {
line.resize(3, ' ');
}
decoded[static_cast<unsigned char>(line[2])] = line[0];
}
string message;
getline(cin, message);
if (!message.empty() && message.back() == '\r') {
message.pop_back();
}
for (unsigned char character : message) {
cout << decoded[character];
}
cout << '\n';
}