RiseOJ – 가축 줄 세우기

설명

농부 존은 매일 8마리의 젖소, Bessie, Buttercup, Belinda, Beatrice, Bella, Blue, Betsy, Sue의 우유를 짠다.

안타깝게도 소들은 꽤 까다로워서, 농부 존이 $$N$$ 개의 제약 조건( $1 \leq N \leq 7$ )을 지키는 순서로 우유를 짜 주기를 요구한다. 각 제약 조건은 " $$X$$ must be milked beside $$Y$$ "의 형태로, 소 $$X$$ 가 우유 짜기 순서에서 소 $$Y$$ 의 바로 뒤 또는 바로 앞에 와야 한다는 뜻이다.

농부 존이 이 필수 제약 조건들을 모두 만족하는 소들의 순서를 결정하도록 도와주자. 그러한 순서는 항상 존재함이 보장된다. 가능한 순서가 여러 개라면, 알파벳순으로 가장 앞서는 것을 출력한다. 즉, 첫 번째 소는 유효한 어떤 순서에서든 맨 앞에 올 수 있는 모든 소 중 알파벳순으로 가장 앞서는 이름이어야 한다. 이 알파벳순으로 가장 앞서는 소로 시작하는 모든 순서 중에서, 두 번째 소는 가능한 모든 유효한 순서 중 알파벳순으로 가장 앞서야 하며, 이후에도 같은 방식으로 이어진다.

문제 제공: Brian Dean

제약

문제 제공: Brian Dean

입력 형식

첫째 줄에 $$N$$ 이 주어진다. 다음 $$N$$ 개의 줄에는 각각 " $$X$$ must be milked beside $$Y$$ " 형태로 제약 조건을 설명하는 문장이 주어지며, $$X$$ 와 $$Y$$ 는 농부 존의 소들의 이름이다(가능한 여덟 개의 이름은 위에 나열되어 있다).

출력 형식

모든 제약 조건을 만족하는 소들의 순서를 한 줄에 한 마리씩, 8개의 줄로 출력한다. 가능한 순서가 여러 개라면, 알파벳순으로 가장 앞서는 것을 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 lineup.in · 출력을 쓸 파일 lineup.out

예제 1

입력

3
Buttercup must be milked beside Bella
Blue must be milked beside Bella
Sue must be milked beside Beatrice

출력

Beatrice
Sue
Belinda
Bessie
Betsy
Blue
Bella
Buttercup

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2019-2020 > December > Bronze

올림피아드 > USACO > 2019-2020 > December > Bronze

태그

JudgeUSACO

가축 줄 세우기

평가 및 의견

풀이 제출