GHOST 단어 게임

GHOST는 지루한 학생들이 긴 이동 중에 즐기는 철자 게임이다. 목표는 어떤 단어의 시작 부분이 되도록 글자를 이어 붙이되, 실제로 단어를 완성하지는 않는 것이다. 게임을 시작하기 전에 참가자들은 차례 순서를 정한다. 차례는 한 사람에서 다음 사람으로 넘어가고, 마지막 사람 다음에는 다시 첫 번째 사람으로 돌아오며 게임이 끝날 때까지 반복된다. 자기 차례에 각 참가자는 다음 세 가지 중 정확히 하나를 해야 한다: 현재 글자열을 늘리기, 허풍 치기, 이의 제기하기.

1. 늘리기. 가장 흔한 수는 현재 글자열 뒤에 한 글자를 붙여, 그 결과가 여전히 어떤 단어의 시작 부분이 되게 하는 것이다. 예를 들어 첫 번째 사람이 (속으로 part를 생각하며) P를, 두 번째 사람이 (play를 생각하며) L을, 세 번째 사람이 (please를 생각하며) E를 부를 수 있다. 실제로 4글자 이상인 올바른 단어를 완성한 사람은 진다. 참가자가 세 명뿐일 때 PLE 다음에 첫 번째 사람이 (plead를 노리고) A를 붙이면, 이미 plea가 올바른 단어이므로 진다.
2. 허풍. 붙일 만한 올바른 글자가 떠오르지 않는 사람은 아무 글자나 불러 다음 사람이 눈치채지 못하기를 기대할 수 있다.
3. 이의 제기. 바로 앞 사람이 허풍을 쳤거나 단어를 완성했다고 의심되면 그 사람에게 이의를 제기할 수 있다. 현재 글자열이 4글자 이상인 단어를 완성한 것이라고 모두가 동의하면 앞 사람이 진다. 앞 사람이 현재 글자열로 시작하는 단어를 대지 못하면 앞 사람이 진다. 현재 글자열이 완성된 단어가 아니고 앞 사람이 그것으로 시작하는 단어를 댈 수 있으면 이의를 제기한 사람이 진다.

컴퓨터 참가자로서 GHOST의 한 차례를 두는 프로그램을 작성하라. 뛰어난 참가자는 단순히 올바른 확장 글자 하나를 찾는 데 그치지 않고, 그 글자열이 자라날 수 있는 모든 단어를 참가자 수와 견주어, 훗날 자기 차례에 어쩔 수 없이 단어를 완성하게 되는 일이 없도록 한다.

입력은 하나 이상의 시나리오로 이루어진다.

각 시나리오는 다음과 같이 주어진다.

• 한 줄에 정수 하나: 참가자 수. 올바른 시나리오라면 $2$ 이상이다. $2$보다 작은 값은 입력의 끝을 나타낸다.
• 이 시나리오의 사전: 한 줄에 한 단어씩 나열된다. 모든 단어는 a–z 글자로만 이루어지며, 앞뒤나 중간에 공백이 없다. 빈 줄이 단어 목록의 끝을 알린다.
• 그 다음 한 줄에 현재 글자열이 앞뒤 공백 없이 주어진다. 이 글자열은 (컴퓨터가 첫 번째로 두는 경우) 비어 있을 수 있고, (모든 참가자가 이미 한 번 이상 두었다면) 참가자 수보다 길 수도 있다.

각 시나리오마다 정확히 한 줄을 출력한다. 입력에 주어진 현재 글자열, 그 뒤에 공백 하나, 그 뒤에 다음 중 하나를 이어 쓴다.

• Challenge — 현재 글자열 자체가 사전에 있는 단어이거나, 사전의 어떤 단어의 접두사도 아닐 때.
• 한 글자 — 올바른 확장. 컴퓨터는 지금 $\text{len}+1$번째 위치의 글자를 두려 한다(위치는 $1$부터 센다). 따라서 컴퓨터는 $p \equiv (\text{len}+1) \pmod{k}$인 모든 위치 $p$를 두게 되며, 여기서 $k$는 참가자 수, $\text{len}$은 현재 글자열의 길이다. 글자 c가 올바른 확장이 되려면: 글자열 뒤에 c를 붙인 것이 어떤 단어의 접두사여야 하고; 그 확장된 글자열 자체가 4글자 이상인 단어를 완성해서는 안 되며; 확장된 글자열로 시작하는 사전의 단어 $W$가 있어, $W$의 남은 글자들을 한 차례에 하나씩 이어 쓸 때 도중에 처음으로 완성되는 4글자 이상 단어가 컴퓨터의 차례에 놓이지 않아야 한다. 조건을 만족하는 글자가 여럿이면 사전순으로 가장 앞선 글자를 출력한다.
• Bluff — 확장이 하나 이상 존재하지만, 모든 확장이 결국 컴퓨터 자신이 단어를 완성하도록 몰아넣을 때.