Compress Binary Runs
National Olympiad — Regional round (2013 season)
Submission name: compression.cpp
Problem summary
Scan a binary sequence from left to right, replacing 1 by a, 01 by b, 001 by c, and so on through 25 zeroes followed by 1 becoming z. A final period terminates the input.
Source clarification. The PDF provides no length limit and does not define an encoding for trailing zeroes or runs exceeding 25 zeroes. The solution follows the explicitly described encodable input domain without assigning invented outputs outside it.
Input
A binary sequence followed by a period.
Output
Its encoded sequence of lowercase Latin letters.
Constraints
No total length bound is printed. The described encoding covers runs of 0…25 zeroes terminated by 1; trailing zeroes and longer runs are not assigned an encoding.
Worked example
An independently prepared example for this explanation.
Input
101001.
Output
abc
Solution analysis
- Count zeroes since the last 1. When a 1 arrives, its block contains that many zeroes followed by 1, so output the letter a+zeroCount.
- Reset the zero counter after each 1. Stop at the period; it is not part of the binary data. Streaming avoids depending on any missing total length bound.
- 101001 splits into 1,01,001. Their zero counts 0,1,2 produce a,b,c, hence abc.
Why it works
Before each input character, the counter is the length of the unfinished zero run. On a 1, the block is complete and the prescribed letter is exactly a plus its zero count. Resetting starts the next block, so all encodable blocks are emitted correctly in order.
Watch out. Reset the counter after a 1. Do not encode the final period. Inputs with unencodable runs have no specified output.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
using namespace std;
int main() {
char symbol;
int zeroes = 0;
while (cin >> symbol && symbol != '.') {
if (symbol == '0') {
zeroes++;
} else {
// A terminating 1 completes the current zero-run block.
cout << static_cast<char>('a' + zeroes);
zeroes = 0;
}
}
cout << '\n';
}