시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 16 | 13 | 13 | 81.250% |
You are playing a culture simulation game, in which your culture can develop various technologies. Some technologies depend upon others; if technology A depends upon technology B, you cannot develop B until you have developed A. Your culture can work on only one technology at a time.
In the game, you have goals which require particular technologies. You have decided to write a program to help you by planning out the order in which to develop technologies.
The input to your program starts with the number of test cases, T, on a line by itself. T test cases follow. Each one consists of:
Each technology name is a sequence of alphanumeric characters (letters or numbers). Technology names are case-sensitive.
The output for each case should start with a line of the form "Case #C: D", where C is the case number, starting from 1, and D is the smallest possible number of technologies that have to be researched. The next D lines should each contain one technology, in the order that they need to be researched.
If there are several possible correct orderings, any one of them is acceptable.
4 9 Metalworking:Fire Pottery:Fire Iron:Metalworking Steel:Iron Battleships:Steel Alchemy:Fire Chemistry:Alchemy Explosives:Chemistry Battleships:Explosives 1 Battleships 9 Metalworking:Fire Pottery:Fire Iron:Metalworking Steel:Iron Battleships:Steel Alchemy:Fire Chemistry:Alchemy Explosives:Chemistry Battleships:Explosives 2 Metalworking Pottery 2 b:a c:b 1 d 1 A:a 1 A
Case #1: 8 Fire Metalworking Iron Steel Alchemy Chemistry Explosives Battleships Case #2: 3 Fire Pottery Metalworking Case #3: 1 d Case #4: 2 a A
Contest > Google > Google's Coding Competitions > EuroPython 2012 > EuroPython 2012 D2번