Problem:


Problem A: Strange String Manipulation

A linear congruential generator produces a series R(&sdot;) of pseudo-random numbers by the following for-
mulas:

where S, A, C, and M are all parameters. In this problem, 0 ≤ S, A, C ≤ 15 and M = 256.

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

Your task is to write a program that shows the parameters S, A, and C such that the information entropy of the output string O(&sdot;) is minimized. Here, the information entropy H is given by the following formula:

where N is the length of the string and #(x) is the number of occurences of the alphabet x.

Input

The input consists of multiple datasets. Each dataset has the following format:

N

I(1) I(2) ... I(N)

N does not exceed 256.

The last dataset is followed by a line containing one zero. This line is not a part of any dataset and should not be processed.

Output

For each dataset, print in a line the values of the three parameters S, A, and C separated by a single space. If more than one solution gives the same minimum entropy, choose the solution with the smallest S, A, and then C.

Sample Input

5
5 4 3 2 1
5
7 7 7 7 7
10
186 8 42 24 154 40 10 56 122 72
0

Output for the Sample Input

0 1 1
0 0 0
8 7 14



Sample input:
5
5 4 3 2 1
5
7 7 7 7 7
10
186 8 42 24 154 40 10 56 122 72
0


Sample output:
0 1 1
0 0 0
8 7 14

Submission status: Wrong Answer

Solution code:
import math
M = 256
while 1:
    N = int(raw_input())
    if N == 0: break
    H = 1e10
    I = map(int,raw_input().split())
    for S in range(16):
        for A in range(16):
            for C in range(16):
                R = S
                O = [0]*M
                for i in I:
                    R = (A*R+C)%M
                    O[(i+R)%M] += 1
                tmp = -sum(1.0*x/N*math.log(1.0*x/N) for x in O if x > 0)
                if tmp < H:
                    H = tmp
                    ans = [S,A,C]
    print " ".join(map(str,ans))

Submission status: Wrong Answer

Solution code:
import sys
import collections
import math

while True:
    N = int(raw_input())
    if N == 0:
        break
    
    I = map(int, raw_input().split())
    M = 256
    result = []
    for S in xrange(16):
        for A in xrange(16):
            for C in xrange(16):
                R = [S]
                for i in xrange(N):
                    R.append((A * R[i] + C) % M)

Submission status: Wrong Answer

Solution code:
import sys
import collections
import math

while True:
    N = int(raw_input())
    if N == 0:
        break
    
    I = map(int, raw_input().split())
    M = 256
    result = []
    for S in xrange(16):
        for A in xrange(16):
            for C in xrange(16):
                R = [S]
                for i in xrange(N):
                    R.append((A * R[i] + C) % M)
                O = []
                for i in xrange(N):
                    O.append((I[i] + R[i + 1]) % M)
                count = collections.Counter()
                count.update(O)

Submission status: Accepted

Solution code:
import math
M = 256
while 1:
    N = int(raw_input())
    if N == 0: break
    H = 1e10
    l = map(int,raw_input().split())
    ans = [0,0,0]
    for S in range(16):
        for A in range(16):
            for C in range(16):
                R = S
                O = [0]*N
                for i in range(N):
                    R = (A*R+C)%M
                    O[i] = (l[i]+R)%M
                L = [0]*256
                for i in O: L[i] += 1
                tmp = -sum(float(i)/N*math.log(float(i)/N,2) for i in L if i != 0)
                if tmp < H:
                    H = tmp
                    ans = [S,A,C]
    print " ".join(map(str,ans))

Submission status: Accepted

Solution code:
import math
M = 256
while 1:
    N = int(raw_input())
    if N == 0: break
    H = 1e10
    l = map(int,raw_input().split())
    ans = [0,0,0]
    for S in range(16):
        for A in range(16):
            for C in range(16):
                R = S
                O = [0]*256
                for i in range(N):
                    R = (A*R+C)%M
                    O[(l[i]+R)%M] += 1
                tmp = -sum(float(x)/N*math.log(float(x)/N,2) for x in O if x != 0)
                if tmp < H:
                    H = tmp
                    ans = [S,A,C]
    print " ".join(map(str,ans))

Submission status: Accepted

Solution code:
import math
M = 256
while 1:
    N = int(raw_input())
    if N == 0: break
    H = 1e10
    l = map(int,raw_input().split())
    for S in range(16):
        for A in range(16):
            for C in range(16):
                R = S
                O = [0]*M
                for i in range(N):
                    R = (A*R+C)%M
                    O[(l[i]+R)%M] += 1
                tmp = -sum(1.0*x/N*math.log(1.0*x/N,2) for x in O if x != 0)
                if tmp < H:
                    H = tmp
                    ans = [S,A,C]
    print " ".join(map(str,ans))

Submission status: Accepted

Solution code:
import math
M = 256
while 1:
    N = int(raw_input())
    if N == 0: break
    H = 1e10
    I = map(int,raw_input().split())
    for S in range(16):
        for A in range(16):
            for C in range(16):
                R = S
                O = [0]*M
                for i in I:
                    R = (A*R+C)%M
                    O[(i+R)%M] += 1
                tmp = -sum(1.0*x/N*math.log(1.0*x/N,2) for x in O if x > 0)
                if tmp < H:
                    H = tmp
                    ans = [S,A,C]
    print " ".join(map(str,ans))

Submission status: Accepted

Solution code:
import math,itertools as it
M = 256
while 1:
    N = int(raw_input())
    if N == 0: break
    H = 1e10
    I = map(int,raw_input().split())
    for S,A,C in it.product(range(16),repeat=3):
        R = S
        O = [0]*M
        for i in I:
            R = (A*R+C)%M
            O[(i+R)%M] += 1
        tmp = -sum(1.0*x/N*math.log(1.0*x/N,2) for x in O if x > 0)
        if tmp < H:
            H = tmp
            ans = [S,A,C]
    print " ".join(map(str,ans))

Submission status: Accepted

Solution code:
import math
M = 256

def entropy_if_smallest(ctr,bound):
    ret = 0
    for v in ctr:
        if v == 0: continue
        ret -= (v / N) * math.log2(v / N)
        if ret >= bound:
            return None
    return ret

def solve(src):
    ans_h = float('inf')
    ans = None
    for s in range(16):
        for a in range(16):
            for c in range(16):
                ctr = [0] * M
                r = s
                for i in src:
                    r = (a*r + c) % M
                    o = (i + r) % M
                    ctr[o] += 1
                h = entropy_if_smallest(ctr,ans_h)
                if h is not None:
                    ans = (s,a,c)
                    ans_h = h
                    if ans_h == 0:
                        return ans
    return ans

while True:
    N = int(input())
    if N == 0: break
    src = list(map(int,input().split()))
    print(' '.join(map(str,solve(src))))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 998244353

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    while True:
        n = I()
        if n == 0:
            break

        ii = LI()
        m = inf
        r = '-1'
        for s in range(16):
            for a in range(16):
                for c in range(16):
                    t = s
                    f = [0] * 256
                    for i in ii:
                        t = (a * t + c) % 256
                        f[(t + i) % 256] += 1
                    h = 0
                    for i in range(256):
                        if f[i] == 0:
                            continue
                        h -= f[i] / n * math.log(f[i] / n)
                    if m > h + eps:
                        m = h
                        r = '{} {} {}'.format(s, a, c)

        rr.append(r)


    return '\n'.join(map(str, rr))


print(main())

Submission status: Accepted

Solution code:
import math
def prodR(s,a,c,N):
    R=[s]
    for i in range(1,N+1):
        R.append((a*R[i-1]+c)%256)
    return R[1:]

def entropy(R,I,N):
    O=[(I[i]+R[i])%256 for i in range(N)]
    L=[0]*256
    for i in O:
        L[i]+=1
    H=-sum(float(L[i])/N*math.log(float(L[i])/N,2) for i in range(256) if L[i]!=0)
    return H

while True:
    N=input()
    if N==0:break
    I=map(int,raw_input().split())
    maxInt=1e10
    for s in range(16):
        for a in range(16):
            for c in range(16):
                R=prodR(s,a,c,N)
                H=entropy(R,I,N)
                if maxInt>H:
                    maxInt=H
                    ans=s,a,c
    print "%d %d %d"%(ans[0],ans[1],ans[2])

Submission status: Accepted

Solution code:
import math

M = 256
R = [[[[None]*(M+2) for i in range(16)] for j in range(16)] for k in range(16)]
for s in range(16):
    for a in range(16):
        for c in range(16):
            R[s][a][c][0] = s
            for i in range(M+1):
                R[s][a][c][i+1] = (a*R[s][a][c][i]+c)%M

while True:
    n = int(input())
    if n == 0:
        break
    v = list(map(int,input().split()))
    hmin = 1e9
    smin = 0
    amin = 0
    cmin = 0
    for s in range(16):
        for a in range(16):
            for c in range(16):
                cnt = [0]*(M+1)
                for i in range(n):
                    cnt[(v[i]+R[s][a][c][i+1])%M] += 1
                h = 0
                for x in cnt:
                    if x > 0:
                        h -= math.log2(float(x)/n)*x
                if h < hmin:
                    smin,amin,cmin,hmin = s,a,c,h
    print(smin,amin,cmin)

Submission status: Runtime Error

Solution code:
import math
def calcH(O):
    n = len(O)
    return sum(-O.count(x)*1.0/n*math.log(O.count(x)*1.0/n) for x in set(O))
    
M = 256
while 1:
    n = int(raw_input())
    if n == 0: break
    I = map(int,raw_input().split())
    H = 10**10
    for S in range(16):
        for A in range(16):
            for C in range(16):
                O = []
                R = S
                for i in range(n):
                    R = (A*R+C)%M
                    O.append((I[i]+R)%M)
                tH = calcH(O)
                if tH < H:
                    H = tH
                    ans = [S,A,C]
    print " ".join(map(str,ans))

Submission status: Runtime Error

Solution code:
import math
def calcH(O):
    n = len(O)
    return sum(-O.count(x)*1.0/n*math.log(O.count(x)*1.0/n) for x in set(O))

M = 256
while 1:
    n = int(raw_input())
    if n == 0: break
    I = map(int,raw_input().split())
    H = 10**10
    for S in range(16):
        for A in range(16):
            for C in range(16):
                O = [0]*n
                R = S
                for i in range(n):
                    R = (A*R+C)%M
                    O[i] = (I[i]+R)%M
                tH = calcH(O)
                if tH < H:
                    H = tH
                    ans = [S,A,C]
    print " ".join(map(str,ans))

Submission status: Runtime Error

Solution code:
import math
M = 256
while 1:
    N = int(raw_input())
    if N == 0: break
    H = 10**10
    l = map(int,raw_input().split())
    for S in range(16):
        for A in range(16):
            for C in range(16):
                R = S
                O = [0]*N
                for i in range(N):
                    R = (A*R+C)%M
                    O[i] = (l[i]+R)%M
                tmp = -sum(1.0*O.count(x)/N*math.log(1.0*O.count(x)/N) for x in set(O))
                if tmp < H:
                    H = tmp
                    ans = [S,A,C]
    print " ".join(map(str,ans))

Submission status: Runtime Error

Solution code:
import math
M = 256
while 1:
    N = int(raw_input())
    if N == 0: break
    H = 1
    l = map(int,raw_input().split())
    for S in range(16):
        for A in range(16):
            for C in range(16):
                R = S
                O = [0]*N
                for i in range(N):
                    R = (A*R+C)%M
                    O[i] = (l[i]+R)%M
                X = [O.count(i) for i in O]
                tmp = -sum(float(x)/N*math.log(float(x)/N) for x in X)
                if tmp < H:
                    H = tmp
                    ans = [S,A,C]
    print " ".join(map(str,ans))

Submission status: Runtime Error

Solution code:
import math
M = 256
while 1:
    N = int(raw_input())
    if N == 0: break
    H = 1
    l = map(int,raw_input().split())
    for S in range(16):
        for A in range(16):
            for C in range(16):
                R = S
                O = [0]*N
                for i in range(N):
                    R = (A*R+C)%M
                    O[i] = (l[i]+R)%M
                X = [O.count(i) for i in set(O)]
                tmp = -sum(float(x)/N*math.log(float(x)/N) for x in X)
                if tmp < H:
                    H = tmp
                    ans = [S,A,C]
    print " ".join(map(str,ans))

Submission status: Runtime Error

Solution code:
import math
M = 256
while 1:
    N = int(raw_input())
    if N == 0: break
    H = 1e32
    l = map(int,raw_input().split())
    for S in range(16):
        for A in range(16):
            for C in range(16):
                R = S
                O = [0]*N
                for i in range(N):
                    R = (A*R+C)%M
                    O[i] = (l[i]+R)%M
                X = [O.count(i) for i in set(O)]
                tmp = -sum(float(x)/N*math.log(float(x)/N) for x in X)
                if tmp < H:
                    H = tmp
                    ans = [S,A,C]
    print " ".join(map(str,ans))

Submission status: Runtime Error

Solution code:
import math
M = 256
while 1:
    N = int(raw_input())
    if N == 0: break
    H = 1e10
    l = map(int,raw_input().split())
    for S in range(16):
        for A in range(16):
            for C in range(16):
                R = S
                O = [0]*N
                for i in range(N):
                    R = (A*R+C)%M
                    O[i] = (l[i]+R)%M
                X = [O.count(i) for i in set(O)]
                tmp = -sum(float(x)/N*math.log(float(x)/N,2) for x in X)
                if tmp < H:
                    H = tmp
                    ans = [S,A,C]
    print " ".join(map(str,ans))

Submission status: Runtime Error

Solution code:
import math
from collections import Counter
M = 256

def entropy(ctr):
    ret = 0
    for v in ctr.values():
        ret -= (v / N) * math.log2(v / N)
    return ret

while True:
    N = int(input())
    if N == 0: break
    src = list(map(int,input().split()))
    ans_h = float('inf')
    ans_sac = None
    for s in range(16):
        for a in range(16):
            for c in range(16):
                ctr = Counter()
                r = s
                for i in src:
                    r = (a*r + c) % M
                    o = (i + r) % M
                    ctr.update([o])
                h = entropy(ctr)
                if h < ans_h:
                    ans_h = h
                    ans_sac = (s,a,c)
    print(' '.join(map(str,ans_sac)))

Submission status: Runtime Error

Solution code:
import math
from collections import Counter
M = 256

def entropy(ctr):
    ret = 0
    for v in ctr.values():
        ret -= (v / N) * math.log2(v / N)
    return ret

def solve(src):
    ans_h = float('inf')
    ans = None
    for s in range(16):
        for a in range(16):
            for c in range(16):
                ctr = Counter()
                r = s
                for i in src:
                    r = (a*r + c) % M
                    o = (i + r) % M
                    ctr.update([o])
                h = entropy(ctr)
                if h < ans_h:
                    ans = (s,a,c)
                    ans_h = h
                    if ans_h == 0:
                        return ans
    return ans

while True:
    N = int(input())
    if N == 0: break
    src = list(map(int,input().split()))
    print(' '.join(map(str,solve(src))))

Submission status: Runtime Error

Solution code:
import math
from collections import Counter
M = 256

def entropy_if_smallest(ctr,bound):
    ret = 0
    for v in ctr.values():
        ret -= (v / N) * math.log2(v / N)
        if ret >= bound:
            return None
    return ret

def solve(src):
    ans_h = float('inf')
    ans = None
    for s in range(16):
        for a in range(16):
            for c in range(16):
                ctr = Counter()
                r = s
                for i in src:
                    r = (a*r + c) % M
                    o = (i + r) % M
                    ctr.update([o])
                h = entropy_if_smallest(ctr,ans_h)
                if h is not None:
                    ans = (s,a,c)
                    ans_h = h
                    if ans_h == 0:
                        return ans
    return ans

while True:
    N = int(input())
    if N == 0: break
    src = list(map(int,input().split()))
    print(' '.join(map(str,solve(src))))

Submission status: Runtime Error

Solution code:
import sys
import collections
import math

while True:
    N = int(raw_input())
    if N == 0:
        break
    
    I = map(int, raw_input().split())
    M = 256
    result = []
    for S in xrange(16):
        for A in xrange(16):
            for C in xrange(16):
                R = [S]
                for i in xrange(N):
                    R.append((A * R[i] + C) % M)
                O = []
                for i in xrange(N):
                    O.append((I[i] + R[i + 1]) % M)
                count = collections.Counter()
                count.update(O)
                H = 0
                for c in count.values():
                    H -= c / float(N) * math.log(c / float(N))
                result.append((H, S, A, C))
    result.sort()
    print ' '.join(map(str, result[0][1:]))

Submission status: Runtime Error

Solution code:
import sys
import collections
import math

while True:
    N = int(raw_input())
    if N == 0:
        break
    
    I = map(int, raw_input().split())
    M = 256
    result = []
    for S in xrange(16):
        for A in xrange(16):
            for C in xrange(16):
                R = [S]
                for i in xrange(N):
                    R.append((A * R[i] + C) % M)
                O = []
                for i in xrange(N):
                    O.append((I[i] + R[i + 1]) % M)
                count = collections.Counter()
                count.update(O)
                H = 0
                for c in count.values():
                    H -= c / float(N) * math.log(c / float(N))
                result.append((H, S, A, C))

Submission status: Runtime Error

Solution code:
import sys
import collections
import math

while True:
	N = int(raw_input())
	if N == 0:
		break
	
	I = map(int, raw_input().split())
	M = 256
	result = []
	for S in xrange(16):
		for A in xrange(16):
			for C in xrange(16):
				R = [S]
				for i in xrange(N):
					R.append((A * R[i] + C) % M)
				O = []
				for i in xrange(N):
					O.append((I[i] + R[i + 1]) % M)
				count = collections.Counter()
				count.update(O)
				H = 0
				for c in count.values():
					H -= c / float(N) * math.log(c / float(N))
				result.append((H, S, A, C))
	result.sort()
	print ' '.join(map(str, result[0][1:]))

Submission status: Runtime Error

Solution code:
import sys
import collections
import math

while True:
    N = int(raw_input())
    if N == 0:
        break
    
    I = map(int, raw_input().split())
    M = 256
    result = []
    for S in xrange(16):
        for A in xrange(16):
            for C in xrange(16):
                R = [S]
                for i in xrange(N):
                    R.append((A * R[i] + C) % M)
                count = [0 for i in xrange(M)]
                for i in xrange(N):
                    count[(I[i] + R[i + 1]) % M] += 1
                H = 0
                for c in count:
                    if c != 0:
                        H -= c / float(N) * math.log(c / float(N))
                result.append((H, S, A, C))
    result.sort()
    print ' '.join(map(str, result[0][1:]))

Submission status: Runtime Error

Solution code:
import math
def prodR(s,a,c,N):
    R=[s]
    for i in range(1,N+1):
        R.append((a*R[i-1]+c)%256)
    return R[1:]

def entropy(R,I,N):
    O=[(I[i]+R[i])%256 for i in range(N)]
    L=[0]*256
    for i in O:
        L[i]+=1
    H=-sum(float(L[i])/N*math.log(float(L[i])/N,2) for i in range(256) if L[i]!\
=0)
    return H

while True:
    N=input()
    if N==0:break
    I=map(int,raw_input().split())
    maxInt=1e10
    for s in range(16):
        for a in range(16):
            for c in range(16):
                R=prodR(s,a,c,N)
                H=entropy(R,I,N)
                if maxInt>H:
                    maxInt=H
                    ans=s,a,c
    print "%d %d %d"%(ans[0],ans[1],ans[2])