E-Casino | cho.sh

문제

의사난수 생성기(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$ 에서는 이런 전수 조사가 어림도 없다.