E-Casino

의사난수 생성기(PRNG)는 시드라고 부르는 입력을 받아 난수 비트 수열 $r[0], r[1], \dots$ 을 출력하는 프로그램이다. 각 비트의 값은 0 또는 1이다.

PRNG 하나와 시드 하나를 고정하자. 도박꾼은 출력의 앞부분 $L$개 비트 $r[0], r[1], \dots, r[L-1]$ 을 관찰한 사람(또는 컴퓨터)이다. 도박꾼은 그 PRNG의 알고리즘을 알고 있어서 비트가 만들어지는 내부 과정까지 안다. 모르는 것은 시드뿐이다. 도박꾼은 알고리즘과 관찰한 앞부분만으로 그 뒤에 나올 $r[L], r[L+1], \dots$ 을 예측하려고 한다.

예측하기 어려운 PRNG를 설계하기는 쉽지 않다. E-Casino라는 회사는 다음 방법을 쓴다. 먼저 어떤 자연 현상을 관측해서 긴 난수 비트 수열 $S[0], S[1], \dots, S[N-1]$ 을 만들었다. 배열 $S$는 공개되어 있어서 도박꾼도 읽을 수 있다. 시드는 정수 $k$ ($0 \le k < N$)와 $M$비트 수열 $m = \langle m[0], m[1], \dots, m[M-1] \rangle$ 로 이루어진 순서쌍 $(k, m)$이다. $j = 0, 1, 2, \dots$ 에 대해 출력 비트 $r[j]$는 다음과 같다.

$r[j] = S[(k + j) \bmod N] \oplus m[j \bmod M]$

여기서 $\oplus$는 배타적 논리합이다. 즉 비트 $a$, $b$에 대해 $a \oplus b = (a + b) \bmod 2$이다.

회사는 항상 $N = 2048$, $M = 32$를 쓴다. 대신 매일 아침 E-Casino의 경영진이 모여서 그날 수열을 만드는 데 쓸 비밀 시드 $(k, m)$를 정한다.

당신이 그 도박꾼이라고 하자. 어느 하루의 출력에서 앞의 $2M = 64$개 비트 $r[0], r[1], \dots, r[63]$ 을 관찰했고 배열 $S$의 값도 안다. 그러나 $k$와 $m$은 모른다. 뒤에 나올 비트를 알아내려면 먼저 비밀 시드의 $k$부터 찾아야 한다. 관찰한 비트와 맞아떨어지는 가장 작은 $k$를 구하자.

입력은 한 줄이다. 줄의 앞 $2M$개 문자는 관찰한 비트 $r[0], r[1], \dots, r[2M-1]$이고, 각 비트는 문자 0 또는 1로 적혀 있다. 맨 앞 문자가 $r[0]$이고 그다음이 $r[1]$이다. 이어서 배열 $S$의 시작을 알리는 문자 %가 하나 나온다. % 바로 뒤 문자가 $S[0]$, 그다음이 $S[1]$이며, 줄 끝까지 같은 순서로 $S$가 적혀 있다. 따라서 한 줄의 길이는 $2M + 1 + N$이다.

$N$과 $M$은 따로 주어지지 않는다. %의 위치가 $2M$이고, 그 뒤에 남은 문자 개수가 $N$이다. E-Casino가 실제로 쓰는 값은 $N = 2048$, $M = 32$이고 이때 줄의 길이는 2113이지만, 더 작은 설정으로 만든 입력도 들어온다. 어느 경우든 $1 \le M \le N \le 2048$이다.

관찰한 비트는 항상 어떤 시드에서 나온 것이므로 조건을 만족하는 $k$가 적어도 하나 있다.

비밀 시드의 $k$로 가능한 가장 작은 값을 출력한다.

$N = 10$, $k = 4$, $M = 3$, $m = \langle 1, 0, 1 \rangle$일 때 위 식이 $r[0], r[1], \dots, r[5]$ 를 어떻게 만드는지 표로 따라가 보자. 셋째 줄이 배열 $S$이다. $r[6]$부터 $r[9]$까지는 표를 간결하게 두려고 생략했다.

          j       | 6 7 8 9 0 1 2 3 4 5
   (k + j) mod N  | 0 1 2 3 4 5 6 7 8 9
---------------------------------------
 S[(k + j) mod N] | 1 1 1 0 0 1 0 1 0 1
     m[j mod M]   |         1 0 1 1 0 1
---------------------------------------
         r[j]     |         1 1 1 0 0 0

즉 출력의 앞 여섯 비트는 1, 1, 1, 0, 0, 0이다. 이 여섯 비트만 본 도박꾼은 $k$와 $m$을 몰라도 $k$가 4임을 확인할 수 있다. $(k, m)$의 조합을 모두 적어 놓고 어느 조합이 이 여섯 비트를 만드는지 보면 된다. 다만 $N = 2048$, $M = 32$에서는 이런 전수 조사가 어림도 없다.