UOFTBD - Diablo Bot

no tags 

Maybe you've played Diablo? There are three different character classes: Noobs, Suckers, and Pros. Noobs don't know anything about the game. Suckers think they know how to play. Pros know that the goal of the game is to write a script that will farm for valuable items that they can turn around and sell to Suckers on the black market. Obviously Pros would sell to Noobs if they could, but Noobs don't even know how to buy items.

An obvious piece of prerequisite information for making such a bot is knowing what sorts of items are worth picking up. There are Normal, Magic, Rare, and Set items:

  • Set items always belong to some famous dead person, so they always begin with a word that ends in "'s" (e.g. Andrew's). No other items are special enough to begin this way.
  • Rare items always have names that are two words long.
  • Magic items always have names that are between two and four words long, inclusive. If, and only if, a Magic item has more than two words in its name, then the last two words are "of [something]" (e.g. of Doom).
  • If the first word is "Damaged", the item is a Normal item. Furthermore, any item that could not possibly be Magic, Rare, or Set must also be Normal. No other items are Normal.
  • You may not have played Diablo, but hopefully you still know that a "word" is a maximal substring of non-space characters. Also, letter case is irrelevant.

You have a list of $N$ ($1 \leq N \leq 1000$) item names, and you need to be able to classify these items as accurately as possible. It may not be possible to assign a unique type to each item, but as long as it's not Normal, surely you'll want it. Every item name is a string of no more than 100 characters, containing only alphabetic characters, spaces, and apostrophes. Every name begins and ends with a non-space character.

Input

First line: 1 integer, $N$

Next $N$ lines: The name of the $i$th item, for $i = 1..N$

Output

$N$ lines: The type of the $i$th item (one of "Normal", "Set", "Magic", or "Rare"), or "Not sure, take anyways" (without quotes) if the item's type cannot be determined, but is known not to be Normal, for $i = 1..N$

Example

Input:
7
Somebody's Something of Whatever
stone of jordan
Wirt's Leg
FLAMING TURNIP
Damaged Goods
Sword
Fish shaped volatile organic compounds
Output: Set
Magic
Set
Not sure, take anyways
Normal
Normal
Normal
 

Explanation of Sample:

The first and third items begin with possessives, so they must be Set items. The second item is three words long, and ends in "of [something]" so it must be Magic. The fourth item could be either Rare or Magic. The fifth item begins with "Damaged" so it's Normal. The last two items don't fit the descriptions of Set, Rare, or Magic, so they must be Normal also.


hide comments
fitcat: 2013-06-05 05:42:19

@Mitch: Yes, logic! This is what I want to discuss with the problem setter. :)

Mitch Schwartz: 2013-06-05 05:42:19

I think the problem is simple overall, but "careless" is probably too harsh -- reading carefully is a skill of itself, and probably the main obstacle here along with a bit of logic; but the hard problems usually involve complex derivations, algorithms, or implementations (or a combination).

Last edit: 2013-06-03 08:54:39
fitcat: 2013-06-05 05:42:19

@Mitch, I agree with you about the reasons of "testing" on the input data. What you do should actually be called "verification" or "validity check". :b

Anyway, do you think this problem is simple? If yes, do you think the extremely low AC rate is normal? The first 2 people leaving comments have solved more than 200 problems. Are they both careless?

Mitch Schwartz: 2013-06-05 05:42:19

Testing input data isn't always reverse engineering. It can be testing whether the input meets with your understanding of the problem, and whether the input data is correct or formatted correctly. In particular when working with e.g. Python there are some problems with poor formatting that will cause failure, whereas with scanf() such issues can go unnoticed. And you know there are sometimes cases where the constraints given in the problem are wrong, especially for newer problems.

fitcat: 2013-06-05 05:42:19

The reason why not testing (though I did sometimes) the input data is because it is not "solving" the problem. It is "cracking" it by reverse engineering.

I would like to point out the issue but I will become a spoiler when doing so.

@Problem setter, may I PM you for a discussion?

Mitch Schwartz: 2013-06-05 05:42:19

Why not test the input? It's a new problem and there were comments about possible trickery. I can tell you what I tested: The first was whether there was a case of a line with two spaces in a row (that is, allowing words with zero length). This seemed unlikely but not explicitly disallowed by the problem statement. It turns out that such thing doesn't occur in the input. Then I tested for empty lines, but actually this shouldn't be allowed according to the problem statement (and indeed it doesn't appear in the input).

So in the end I got AC purely based on reading the statement carefully. But I don't know if for non-native English speakers (I don't mean disrespect) there could be some difficulty there. If there is a specific issue you can bring up to improve the clarity, this could be helpful. But it's hard to tell, maybe you're saying the problem statement is unclear, but you haven't pointed out anything specific.

fitcat: 2013-06-05 05:42:19

@Mitch, why did you test the input? Because you thought the input containing something strange, right? This/these strange thing(s) is/are beyond your understanding. Can you get AC by (not testing the input data) only just re-reading the problem description more carefully? I seriously doubt it.

Mitch Schwartz: 2013-06-05 05:42:19

Well I guess you are being vague so as not to spoil, but frankly the way you wrote it -- "the more careful you are, the more WA you will get" -- is nonsense from my point of view. I got WA because of not being careful enough, my next two WA were testing the input to see if it contained anything strange, and then I noticed my error.

fitcat: 2013-06-05 05:42:19

@Mitch, the first 4 AC people got it right the first time. The next 3 are from my region, HK. The 5th one took a lot WA before he got AC. He is the one who hinted another one (6th) and me (7th) from HK. He had to "unlearn" in order to solve it. In fact, the more careful you are, the more WA you will get.

Mitch Schwartz: 2013-06-05 05:42:19

I think it's entirely normal not to get it right the first time, then read more carefully and get it.


Added by:SourSpinach
Date:2013-05-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Written by Wesley May, used in the 2012 UofT ACM Tryouts