USACO 2019 - Dec - Bronze - Livestock Lineup

View as PDF

Submit solution

Points: 0.10 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Suggester:
Problem source:
http://www.usaco.org/index.php?page=viewproblem2&cpid=965
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Mỗi ngày nông dân John vắt sữa 8 con bò của mình, tên Bessie, Buttercup, Belinda, Beatrice, Bella, Blue, Betsy, và Sue.

Tuy nhiên, những con bò này hơi kén chọn và yêu cầu nông dân John phải vắt sữa chúng sao cho mà thỏa mãn ~N~ điều kiện ~(1 \leq N \leq 7)~. Mỗi điều kiện được thể hiện dưới dạng X must be milked beside Y, nghĩa là bò X phải được vắt sữa ngay trước bò Y hoặc ngay sau bò Y.

Hãy giúp Nông dân John tìm ra một cách sắp xếp những con bò của mình sao cho thỏa mãn điều kiện trên. Đảm bảo luôn tồn tại một cách xếp thỏa mãn. Nếu tồn tại nhiều cách sắp xếp, hãy in cách sắp xếp có thứ tự từ điển bé nhất.

Input

Dòng đầu tiên là số nguyên dương ~N~. ~N~ dòng tiếp theo mô tả một điều kiện dưới dạng X must be milked beside Y, trong đó X và Y là tên của bò của John (một trong tám cái tên được liệt kê ở trên).

Output

In ra 8 dòng, mỗi dòng là tên một con bò của John, là một cách sắp xếp những con bò của John thỏa mãn những điều kiện trên. Nếu tồn tại nhiều cách sắp xếp thì hãy in ra cách có thứ tự từ điển bé nhất.

Sample Input

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

Sample Output

Beatrice
Sue
Belinda
Bessie
Betsy
Blue
Bella
Buttercup

Comments

Please read the guidelines before commenting.


There are no comments at the moment.