Úllen Dúllen Doff 2

사진 출처: flickr.com

Lárus는 훌륭한 회사의 중간 관리자이다. 그는 직원 $n$명을 관리하며, 그중 한 명을 제외한 모든 직원은 그의 친척이다.

새로운 업무가 생기면 Lárus는 그 업무를 직원 한 명에게 배정할 책임이 있다. Lárus는 친척들이 해야 하는 일을 최소화하고 싶다. 하지만 매번 단순히 같은 사람을 선택할 수는 없다.

사람들이 Lárus가 친족을 편애한다고 생각하지 않도록, 그는 사람들을 원형으로 세우고 주문을 사용해 업무를 맡을 사람을 무작위로 고른다. 먼저 한 직원을 가리키면서 첫 번째 단어를 외운다. 그런 다음 주문의 나머지 부분을 외우며, 단어를 하나 외울 때마다 오른쪽의 다음 직원을 가리킨다.

주문은 다음과 같다.

Úllen dúllen doff kikke lane koff koffe lane bikke bane úllen dúllen doff.

Lárus는 친척들이 업무를 맡지 않도록 직원들을 어떻게 세울 수 있을까?

채점

직원 수 $n$의 범위는 $1$부터 $20$까지이다. $n$의 가능한 각 값마다 테스트 그룹이 하나씩 존재하며, 각 그룹에는 $5$점이 배정된다. 한 테스트 그룹의 점수를 얻으려면 해당 그룹의 모든 테스트 케이스를 해결해야 한다.

입력의 첫 번째 줄에는 직원 수를 나타내는 정수 하나 $n$이 주어진다. 그다음 $n$개의 줄이 주어지며, 각 줄에는 이름 하나가 주어진다. 첫 번째 이름은 Lárus와 친척 관계가 아닌 직원의 이름이다.

각 이름은 서로 다르며, $1$개에서 $10$개의 영문 소문자로 이루어져 있다고 가정해도 된다.

각 줄에 직원 한 명의 이름을 담아 $n$개의 줄을 출력하되, 어떤 이름도 반복해서는 안 된다. Lárus는 출력한 순서로 직원들을 배치한 뒤 주문을 외워 업무를 받을 직원을 고른다. 출력한 순서로 인해 그의 친척 중 한 명이 선택되면 제출은 오답으로 판정된다.

첫 번째 예제에서 가능한 해답 중 하나는 입력과 같은 순서로 진행하는 것이며, 그 결과 다음과 같은 단계를 거친다.

• Úllen: Arnar

• dúllen: Atli

• doff: Bjarni

• kikke: Bjarki

• lane: Hannes

• koff: Unnar

• koffe: Arnar

• lane: Atli

• bikke: Bjarni

• bane: Bjarki

• úllen: Hannes

• dúllen: Unnar

• doff: Arnar

Arnar가 최종 선택이 되므로 출력은 정답으로 판정된다.

두 번째 예제에서 가능한 답 중 하나는 다음 순서로 진행하는 것이다.

• Úllen: v

• dúllen: x

• doff: y

• kikke: a

• lane: b

• koff: c

• koffe: p

• lane: q

• bikke: r

• bane: s

• úllen: t

• dúllen: u

• doff: z

마지막에는 z가 선택되므로 출력은 정답으로 판정된다.

다른 올바른 출력도 많이 존재하며, 두 번째 예제에서는 주어진 순서의 마지막 두 값까지 도달하지 않는다는 점에 유의한다.