ZOJ Problem Set - 2570
The King, Arthur plans to hold a knight championship all over his country. During the tournament, all his knights will appear one by one on the arena. The knight who appears first is supposed to be the man the arena temporarily at the very beginning. But when the second knight goes into arena, he will then take a challenge to the first knight and the winner of them is the new man of the arena. And then the third, fourth, and so on. Once a new knight enters, there is a fight between the current man of the arena and him to decide who will be the next man, and the loser will be eliminated from the competition. So after all the fights, there will be only one knight left in the arena, who is the champion of all the knights.
King Arthur wants to make this chamionship as nice as possible since there will be a lot of people living in King Arthur's country being the spectators of the matches. All his famous knights will appear in the matches such as Sir Kay, Sir Ector, Gawain and Lancelot. Of cource, Merlin is the referee of the tournament and he suggests King Arthur that the more times man of the arena alters, the more wonderful the games will be. Arthur highly praises this advice but he is sheerly worried whether a too excited game will make his people crazy. So he decides to control the times of alterations of man of the arena on a suitable level.
Now it's time for you to help your King how to arrange the sequence of the kights to meet Arthur's need. King Arthur also wants to know how many choices he has. It is not necessary to worry about who will be the winner in two knights. King Arthur knows the exact power of every knight and the one with more power will always beat his oppenent in each fight.
The input contains several test cases. The first line of each case stands 1 integer N (0 < N <= 100), which means King Arthur has N knights. Then N lines follow with the description of his N knights, where each line decribes one knight. The first word (with 20 letters at the most) of each line is the name of this knight and then there is an integer indicating his power (0 < power < 1000). The name and the power of a knight are different from each other, which means there will never be a draw game during the championship. The last line of a test case stands an integers M indicating there are M integers following in this line, and then M integers Ki (Ki >= 0, 0 <= i < M). Each denotes there are Ki alternations of man of the arena in the whole game Arthur is just considering.
The input ends with a case of N = 0. There is a blank line between cases.
For each Ki (0 <= i < M) in each case, first output the number of arrangment choices Arthur has in one line, And then a line with a sequence of the knights' appearance that meets the King's need. If there is no such an arrangement (that is, the number of choices is zero), output a single word "-_-" in this line. If there are more than one suitable arrangement, output the smallest one.
Note: An sequence A is smaller than another sequence B if the first m - 1 words of both them are the same and the m'th word in A is smaller than the m'th word in B, where 0 < m <= n and n is the number of words in both A and B. A word is smaller than another one if it has a smaller lexicographic order, which should be case-insensitive.
Print a blank line after each case except the last one.
2 Kay 25 Ector 20 2 0 1 3 Ector 20 Gawain 25 Lancelot 30 3 1 0 2 0
1 Kay Ector 1 Ector Kay 3 Ector Lancelot Gawain 2 Lancelot Ector Gawain 1 Ector Gawain Lancelot
Author: JIANG, Hao
Source: ZOJ Monthly, October 2005