Strange String Manipulation
Time limit8sMemory limit512 MB
Given a byte string, search all 4096 parameter triples of a fixed LCG and output the one whose shift minimizes the output string's entropy.
- Level
Medium6 of 10
- Topics
- Brute force, Math, Implementation, Hash map
- Solved
- No attempts yet
Problem
A linear congruential generator produces a series of pseudo-random numbers by the following formulas:
, (for ),
where , , , and are all parameters. In this problem, and .
Now suppose we have some input string , where each character in the string is an integer between and . Then, using the pseudo-random number series , we obtain another string as the output by the following formula:
(for ),
Your task is to write a program that shows the parameters , , and such that the information entropy of the output string is minimized. Here, the information entropy is given by the following formula:
H = -\sum\_{x}{\frac{\text{#}(x)}{N}\log{\frac{\text{#}(x)}{N}} }
where is the length of the string and \text{#}(x) is the number of occurrences of the alphabet .
Input
The input has the following format:
does not exceed 256.
Output
Print in a line the values of the three parameters , , and separated by a single space. If more than one solution gives the same minimum entropy, choose the solution with the smallest , , and then .