This page is still under construction.

Parts of this page are still being built. What you see may change.

Strange String Manipulation

Time limit8sMemory limit512 MB

Summary
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 R(⋅)R(·) of pseudo-random numbers by the following formulas:

R(0)=SR(0) = S, R(i)=(A⋅R(i−1)+C) mod MR(i) = (A · R(i - 1) + C) \bmod M (for i=1,2,…i = 1, 2, \dots),

where SS, AA, CC, and MM are all parameters. In this problem, 0≤S,A,C≤150 \le S, A, C \le 15 and M=256M = 256.

Now suppose we have some input string I(⋅)I(·), where each character in the string is an integer between 00 and (M−1)(M - 1). Then, using the pseudo-random number series R(⋅)R(·), we obtain another string O(⋅)O(·) as the output by the following formula:

O(i)=(I(i)+R(i)) mod MO(i) = (I(i) + R(i)) \bmod M (for i=1,2,…i = 1, 2, \dots),

Your task is to write a program that shows the parameters SS, AA, and CC such that the information entropy of the output string O(⋅)O(·) is minimized. Here, the information entropy HH is given by the following formula:

H = -\sum\_{x}{\frac{\text{#}(x)}{N}\log{\frac{\text{#}(x)}{N}} }

where NN is the length of the string and \text{#}(x) is the number of occurrences of the alphabet xx.

Input

The input has the following format:

NN

I(1)I(2)…I(N)I(1) I(2) \dots I(N)

NN does not exceed 256.

Output

Print in a line the values of the three parameters SS, AA, and CC separated by a single space. If more than one solution gives the same minimum entropy, choose the solution with the smallest SS, AA, and then CC.

Examples3

  1. Example 1

    Input
    5
    5 4 3 2 1
    
    Expected output
    0 1 1
    
  2. Example 2

    Input
    5
    7 7 7 7 7
    
    Expected output
    0 0 0
    
  3. Example 3

    Input
    10
    186 8 42 24 154 40 10 56 122 72
    
    Expected output
    8 7 14