Fibonacci Compression
Time limit1sMemory limit512 MB
Given a string of integer symbols, assign Fibonacci code words by frequency and report the compressed bit length of every prefix.
- Level
Medium7 of 10
- Topics
- Greedy, Sorting, Implementation, Combinatorics
- Solved
- No attempts yet
Problem
Fibonacci compression is a new kind of fault-tolerant compression based on Fibonacci numbers. Symbols are built according to the rule that a code word may not contain two consecutive "1" bits anywhere except at the end, where two "1" bits are mandatory. In practice this means that for each compressed symbol bit-length i with i ≥ 2, there are Fibonacci(i − 1) compressed symbols of that length.
For example, the shortest 14 Fibonacci code words are as follows:
11 011 0011 1011
00011 10011 01011 000011
100011 010011 001011 101011
0000011 1000011 ...
To compress a string with Fibonacci compression, replace the most frequent characters with the shortest codes. Given one such string s, find the length of each of its prefixes when it is compressed as small as possible under this system.
Input
- One line containing the length of the string to compress, n (1 ≤ n ≤ 105).
- One line containing the string s as a sequence of n integers si (0 ≤ si ≤ 106).
Output
Output |s| lines, where the ith line is the compressed length in bits of the first i characters of s.