루미 알고리즘

#1291플래티넘Letter Game

PO 2009 결선코딩영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

Two people, let us call them Anna and Bosse, take turns saying a letter (Anna says the first letter, Bosse the second, Anna the third, and so on). The same letter may be used multiple times. There are two rules:

  • The letters said so far (in order) must not form a completed word.
  • The letters said so far (in order) must be able to form a word if more letters are appended at the end.

The one who breaks either rule loses, and the other one thus wins (in the real game, one can bluff on the second rule).

For example, if the letters S, T, and U have been said, then Bosse loses if he says P since STUP is a word. Furthermore, he loses if he says, e.g., J since no word starts with STUJ. However, the game continues if he says G; Anna then cannot say A since STUGA is a word, but she can say B, thereby forcing Bosse to complete the word STUGBY.

For simplicity, we assume here that only the letters A-Z may be used. Furthermore, there is a dictionary containing all letter combinations that are to be considered words in this particular game. Write a program that determines which letters are “safe” to start with for Anna, i.e., the letters that allow her to win the round regardless of which letters Bosse chooses.

Input

The first line contains an integer N (1 ≤ N ≤ 40000), the number of words in the dictionary.

Then follow N lines with one word on each line. The words are in alphabetical order and are all distinct. Each word consists of at least 1 and at most 20 letters, chosen from the uppercase letters A-Z. Made-up words may also appear.

Output

The program should output an alphabetically sorted list of the letters that have the property that, if Anna starts with the letter, she will be able to win regardless of which letters Bosse chooses (both may of course adapt their choices based on what the other says). The letters should be separated by spaces and appear on a single line.

예제

예제 1

입력
8
FE
FRI
FRIA
KO
SE
STUGA
STUGBY
STUP
출력
K S

출처 표기

출처: Programmeringsolympiaden 2009년 결선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.