카드 게임

이 문제는 대화형 문제다.

토니 스타크는 전투 사이의 여유 시간에 비전과 카드 게임을 즐긴다. 그런데 평범한 카드 게임은 금방 지루해져서, 두 사람은 직접 새로운 게임을 만들기로 했다.

덱에는 1부터 $n$까지 적힌 $n$장의 카드가 있고, 모두 뒷면이 위로 향한 채 탁자에 놓여 있다. 게임을 시작하기 전에 비전이 덱을 충분히 섞은 뒤, 토니 몰래 임의의 $k$장을 뒷면이 아래로 향하도록 뒤집는다. 토니의 과제는 덱을 두 개의 비지 않은 더미로 나누어, 두 더미에 뒷면이 아래로 향한 카드 수가 같게 만드는 것이다. 토니는 덱을 보지 않고 이 과제를 풀어야 한다. 토니는 다음 동작을 수행할 수 있다.

• Reverse: 덱의 맨 위 카드를 뒤집는다.
• Move: 덱의 맨 위 카드를 별도의 더미로 옮긴다.
• Up i: 위에서 $i$번째 자리에 있는 카드를 덱의 맨 위로 옮긴다. 그 위의 $i-1$장은 아래로 밀려난다.
• Finish: 더 이상 덱에 동작을 하지 않겠다고 알린다. 이 메시지는 남은 덱과 분리한 더미에 뒷면이 아래로 향한 카드 수가 같다는 뜻이다.

동작을 할 때마다 심사위원인 비전은 분리한 더미에 뒷면이 아래로 향한 카드가 몇 장 있는지 알려 준다.

다음은 예제에서 가능한 한 가지 진행 과정이다.

• 덱에 카드가 6장 있고, 그중 4장이 뒷면이 아래로 향해 있다.
• 맨 위 카드를 분리한 더미로 옮긴다. 이 카드는 뒷면이 아래로 향해 있었으므로, 심사위원은 분리한 더미에 뒷면이 아래로 향한 카드가 1장 있다고 알려 준다. 덱에는 뒷면이 아래로 향한 카드가 3장 남는다.
• 새 맨 위 카드를 뒤집는다.
• 이 카드를 분리한 더미로 옮긴다. 카드의 뒷면이 위로 향해 있어서 반환값은 바뀌지 않는다. 뒤집기 전 맨 위 카드는 뒷면이 아래로 향해 있었으므로, 덱에는 뒷면이 아래로 향한 카드가 2장 남는다.
• 덱의 네 번째(마지막) 카드를 맨 위로 옮긴다.
• 그 카드를 뒤집는다.
• 분리한 더미로 옮기니 뒷면이 아래로 향해 있다고 심사위원이 알려 준다. 이제 덱과 분리한 더미에 뒷면이 아래로 향한 카드가 각각 2장씩 남았으므로, Finish로 게임을 끝내면 된다. 우리가 이겼다.