|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|5 초||512 MB||32||11||10||32.258%|
You are playing Hangman with your friend Sean. And while you have heard that Sean is very good at taking candy from a baby, he is not as good at this game. Can you take advantage of Sean's imperfect strategy, and make him lose as badly as possible?
+--+ | O | / | \ Mystery word: _ a _ a _ a _ | / \ | +-+---+
Hangman is played as follows:
z. In particular, there are no spaces.
Sean uses a very simple strategy. He makes a list L of the 26 letters in some order, and goes through the list one letter at a time. If there is at least one word in D that (a) has the letter he is thinking of, and (b) is consistent with what you have written down so far and the result of all of Sean's previous guesses, then Sean guesses that letter. Otherwise, he skips it. No matter what, Sean then moves on to the next letter in his list.
Given Sean's list, what word should you choose to make Sean lose as many as points as possible? If several choices are equally good, you should choose the one that appears first in D.
Suppose Sean decides to guess the letters in alphabetical order (i.e., L = "abcdefghijklmnopqrstuvwxyz"), and D contains the words
pajamas. If you choose
pajamas, the game would play out as follows:
_ _ _ _ _ _ _on the blackboard. Based on the number of blanks, Sean knows immediately that the word is either
asince it is first in L, and you reveal all locations of the letter
aon the blackboard:
_ a _ a _ a _.
beven though it is used in
banana. Sean already knows that is not your word.
cbecause it appears in
caravan. It does not appear in the word you actually chose though, so Sean loses a point and nothing more is revealed.
pajamas, so he proceeds to guess
sin order, without losing any more points.
So Sean loses one point if you choose
pajamas. He would have gotten either of the other words without losing any points.
The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing integers N and M, representing the number of words in the dictionary and the number of lists to consider.
The next N lines contain the words in the dictionary, one per line: D1, D2, ..., DN. Each word is an arbitrary sequence of characters
The final M lines contain all of the lists Sean will use, one per line: L1, L2, ..., LM. Each list is exactly 26 letters long, containing each letter exactly once. Sean will use these lists to guess letters as described above.
For each test case, output one line containing "Case #x: w1 w2 ... wM", where x is the case number (starting from 1) and wi is the word you should choose if Sean guesses the letters in order Li. If multiple words cause Sean to lose the same number of points, you should choose the option that appears first in the dictionary.
2 3 2 banana caravan pajamas abcdefghijklmnopqrstuvwxyz etaoisnhrdlcumwfgypbvkjxqz 4 1 potato tomato garlic pepper zyxwvutsrqponmlkjihgfedcba
Case #1: pajamas caravan Case #2: garlic