스냅

스냅(Snap)은 두 명이 하는 카드 게임이다. 덱에는 각 종류의 카드가 여러 장씩 들어 있다. 처음에 두 사람은 덱의 절반씩을 정해진 순서대로 뒷면이 보이게 쌓아 두고, 맨 위에서부터 한 장씩 넘겨 앞면이 보이도록 다른 자리에 쌓는다. 자기 앞의 뒷면 더미가 모두 없어지면, 그때까지 쌓은 앞면 더미를 통째로 뒤집어 새 뒷면 더미로 삼고 계속 진행한다.

두 사람은 완전히 동시에 진행한다. 즉 매 턴마다 두 사람이 정확히 같은 순간에 뒷면 더미의 맨 위 카드를 뒤집는다. 뒤집힌 두 카드의 종류가 같으면 두 사람 모두 "Snap!"을 외치는데, 먼저 외친 사람이 상대의 앞면 더미 전체를 가져와 순서를 그대로 유지한 채 자기 앞면 더미 위에 올린다.

한 사람이 모든 카드를 가질 때까지 게임을 진행하며, 그 사람이 승자이다.

스냅 게임을 시뮬레이션하여 게임이 1000턴 안에 끝나는지, 끝난다면 누가 이기는지 판단하라.

첫째 줄에는 제인(Jane)의 뒷면 더미가 맨 위에서 맨 아래 순서로 주어진다. 둘째 줄에는 존(John)의 뒷면 더미가 역시 맨 위에서 맨 아래 순서로 주어진다. 각 카드 종류는 하나의 알파벳 또는 숫자로 표기한다. 제인과 존은 같은 장수의 카드로 시작하며, 각자 최대 50장이다.

누가 먼저 "Snap!"을 외치는지는 고정된 의사난수 생성기로 정한다. $x_0 = 11$로 두고

$$x_n = (1103515245 \cdot x_{n-1} + 12345) \bmod 2^{31}$$

로 정의한다. "Snap!"을 외칠 때마다 생성기를 한 번 진행시키며, $k$번째 호출에서는 값 $x_k$를 사용한다. $\lfloor x_k / 141 \rfloor$이 짝수이면 제인이 먼저 외치고, 그렇지 않으면 존이 먼저 외친다.

제인이 먼저 외칠 때마다 Snap! for Jane: 뒤에 (존의 더미를 가져온 뒤의) 제인의 앞면 더미를 맨 위에서 맨 아래 순서로 출력한다. 존이 먼저 외칠 때마다 Snap! for John: 뒤에 (제인의 더미를 가져온 뒤의) 존의 앞면 더미를 출력한다. 게임이 끝나면 상황에 맞게 Jane wins. 또는 John wins.를 출력한다. 두 사람이 각각 1000장을 넘겼는데도 게임이 끝나지 않으면 Keeps going and going ...를 출력한다.