当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

2476:Game schedule required

Special Judge 特殊评判
题目描述
Sheikh Abdul really loves football. So you better don't ask how much money he has spent to make famous teams join the annual tournament. Of course, having spent so much money, he would like to see certain teams play each other. He worked out a complete list of games he would like to see. Now it is your task to distribute these games into rounds according to following rules:
  • In each round, each remaining team plays at most one game
  • If there is an even number of remaining teams, every team plays exactly one game
  • If there is an odd number of remaining teams, there is exactly one team which plays no game (it advances with a wildcard to the next round)
  • The winner of each game advances to the next round, the loser is eliminated from the tournament
  • If there is only one team left, this team is declared the winner of the tournament

As can be proved by induction, in such a tournament with n teams, there are exactly n - 1 games required until a winner is determined.
Obviously, after round 1, teams may already have been eliminated which should take part in another game. To prevent this, for each game you also have to tell which team should win.
输入解释
The input contains several test cases. Each test case starts with an integer n (2 <= n <= 1000), the number of teams participating in the tournament. The following n lines contain the names of the teams participating in the tournament. You can assume that each team name consists of up to 25 letters of the English alphabet ('a' to 'z' or 'A' to 'Z').
Then follow n - 1 lines, describing the games the sheikh would like to see (in any order). Each line consists of the two names of the teams which take part in that game. You can assume that it is always possible to find a tournament schedule consisting of the given games.
The last test case is followed by a zero.
输出解释
For each test case, write the game schedule, distributed in rounds.
For each round, first write "Round #X" (where X is the round number) in a line by itself. Then write the games scheduled in this round in the form: "A defeats B", where A is the name of the advancing team and B is the name of the team being eliminated. You may write the games of a round in any order. If a wildcard is needed for the round, write "A advances with wildcard" after the last game of the round, where A is the name of the team which gets the wildcard. After the last round, write the winner in the format shown below. Print a blank line after each test case.
输入样例
3
A
B
C
A B
B C
5
A
B
C
D
E
A B
C D
A E
C E
0
输出样例
Round #1
B defeats A
C advances with wildcard
Round #2
C defeats B
Winner: C

Round #1
A defeats B
C defeats D
E advances with wildcard
Round #2
E defeats A
C advances with wildcard
Round #3
E defeats C
Winner: E
提示
Note that there is always more than one possible game schedule; you may print any of them.
Huge input and output,scanf and printf is recommended.

该题目是Virtual Judge题目,来自 北京大学POJ

题目来源 Ulm Local 2005

源链接: POJ-2476

最后修改于 2020-10-29T06:33:36+00:00 由爬虫自动更新

共提交 1

通过率 0.0%
时间上限 内存上限
1500 65536