-
Notifications
You must be signed in to change notification settings - Fork 0
Online round 1: sub round a
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?
당신은 친구 Sean과 Hangman이라는 게임을 하고있습니다. 아마 동생한테 캔디 뺏기를 잘하던 Sean에 대해 들어봤을꺼에요. 하지만 그는 이 게임은 잘 못해요. Sean이 추론하는 방식을 파악하여 그가 가능한한 나쁘게 지도록 하는게 가능할까요?
+--+
| O
| /|\ Mystery word: _ a _ a _ a _
| /
|
+-+---+
Hangman은 다음과 같은 방식으로 진행됩니다.
There is a dictionary D of all valid words, which both you and Sean know. A word consists only of the characters a - z. In particular, there are no spaces.
사전 D에 단어들이 있구요. Sean과 당신이 모두 알고 있습니다. 단어들은 a-z로 이루어져 있구요. 공백은 없습니다.
You begin by choosing any word from D, and writing it down on a blackboard with each letter replaced by a blank: _. On his turn, Sean can choose any letter and ask you if it is in the word. If it is, you reveal all locations of that letter. Otherwise, Sean loses a point.
당신은 사전에서 하나의 단어를 선택합니다. 그리고 칠판에 _로 각각은 글자를 표시합니다. Sean의 차례가 되었을 때, Sean은 글자 하나를 선택하여 그 글자가 단어 안에 포함되어 있는지 당신에게 묻습니다. 당신은 단어 안에 포함되어 있는 글자를 보여줍니다.
Once all letters in the word have been revealed, the round ends.
단어 안의 모든 글자가 들어나면 게임은 끝이 납니다.
The round never ends early, no matter how many points Sean loses.
Sean이 아무리 많은 점수를 잃어도 게임은 끝나지 않습니다.
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.
Sean은 매우 간단한 전략을 사용합니다. 26글자로 이루어진 L이라는 목록을 만들어놓고 그 순서에 따라 하나씩 묻습니다. Bla~ Bla~
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.
Example
Suppose Sean decides to guess the letters in alphabetical order (i.e., L = "abcdefghijklmnopqrstuvwxyz"), and D contains the words banana, caravan, and pajamas. If you choose pajamas, the game would play out as follows:
You begin by writing 7 blanks _ _ _ _ _ _ _ on the blackboard. Based on the number of blanks, Sean knows immediately that the word is either caravan or pajamas. Sean begins by guessing a since it is first in L, and you reveal all locations of the letter a on the blackboard: _ a _ a _ a _. Sean skips b even though it is used in banana. Sean already knows that is not your word. He then guesses c because 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. By process of elimination, Sean now knows your word has to be pajamas, so he proceeds to guess j, m, p, and s in 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. Input
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 a - z.
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.
Output
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.
Limits
1 ≤ T ≤ 10. Each word in D will have between 1 and 10 characters inclusive. No two words in D will be the same within a single test case. Small dataset
1 ≤ N ≤ 100. 1 ≤ M ≤ 10.
Large dataset
1 ≤ N ≤ 10000. 1 ≤ M ≤ 100.
Sample
+-------------------------------+-----------------------------+
| Input | Output |
+-------------------------------+-----------------------------+
| 2 | Case #1: pajamas caravan |
| 3 2 | Case #2: garlic |
| banana | |
| caravan | |
| pajamas | |
| abcdefghijklmnopqrstuvwxyz | |
| etaoisnhrdlcumwfgypbvkjxqz | |
| 4 1 | |
| potato | |
| tomato | |
| garlic | |
| pepper | |
| zyxwvutsrqponmlkjihgfedcba | |
+-------------------------------+-----------------------------+
You are playing a game with a fancy deck of cards. Each card has three bonus numbers: a card bonus c, a score bonus s, and a turn bonus t. Some of the cards start in your hand, while the rest are in a deck on the table. You start with one turn.
On each turn, you can choose any card from your hand and play it. If it has bonus numbers c, s, t, then the following happens:
- The card is discarded from your hand, and it can never be used again.
- You draw the first c cards from the deck into your hand. If the deck has fewer than c cards in it, you draw all of them.
- Your total score increases by s.
- Your number of remaining turns increases by t. If you do not have any cards in your hand at the start of a turn, then nothing happens on that turn. Your goal is to get as high a score as possible before running out of turns.
For example, suppose your hand and deck contain the following cards:
+---+---+---+ +---+---+---+
HAND: | c | s | t | DECK: | c | s | t |
+---+---+---+ +---+---+---+
Card #1: | 0 | 0 | 2 | Card #4: | 1 | 1 | 0 |
Card #2: | 0 | 5 | 0 | Card #5: | 0 | 1 | 1 |
Card #3: | 2 | 1 | 1 | Card #6: | 2 | 2 | 0 |
+---+---+---+ +---+---+---+
The following table shows how you can get a score of 8 from these cards. The first three columns show your hand, the number of turns left, and your score before playing each card, and the final column shows which card to play.
+---------+------------+-------+------+
| Hand | Turns left | Score | Play |
+---------+------------+-------+------+
| 1, 2, 3 | 1 | 0 | 1 |
| 2, 3 | 2 | 0 | 3 |
| 2, 4, 5 | 2 | 1 | 2 |
| 4, 5 | 1 | 6 | 5 |
| 4 | 1 | 7 | 4 |
| 6 | 0 | 8 | - |
+---------+------------+-------+------+
As you can see, the card bonuses and turn bonuses allow you to chain together a long sequence of cards before you have to stop.