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
Chandan Mittal: 2013-06-09 11:13:01

@p-setter
can there be multiple spaces between names or spaces at the beginning/end of string???

RE: As the problem states, not at the start or end. But nothing else is promised.

Last edit: 2013-06-10 06:25:13
fitcat: 2013-06-05 05:42:19

@numerix: Based on what you asked, you are following exactly the same path of me :)

Federico Lebrón: 2013-06-05 05:42:19

I'm not a native English speaker, and the reason I didn't WA is because I saw that if the code wasn't going to be a challenge, then understanding the solution had to be. So I read slowly, and translated words into formal logic, then formal logic into code.

My suggestion: It's easy to make test cases for this, so take advantage of that. Write test cases you don't know the answer to, and think what the answer should be. Make your code reflect the thought process you had while figuring out the right answer for each test case.

Wesley May: 2013-06-05 05:42:19

Yes, only characters in the range [a-z] and [A-Z], not that it should matter. And yes, two words long means two words long.

numerix: 2013-06-05 05:42:19

@Wesley: Thanks for clarification.
Another question: "only alphabetic characters" refers to English alphabet (no ñ or ä or something like that)?
And another one: "two words long" (Rare items) means "exactly two words long"?

Last edit: 2013-06-04 20:19:11
Wesley May: 2013-06-05 05:42:19

@fitcat: maybe easiest to just email me at my GMail account (username: wjomlex). The forum is acting up for me.

@numerix:
1. I'll make it say "inclusive" to be more clear, thanks.
2/3. The string "apple" begins with the string "apple". It also ends with the string "apple".

numerix: 2013-06-05 05:42:19

After several WAs it seems that I'm one of those unable to read ...
Perhaps the following questions can be answered without spoiling:
1. In my native language (German) the word "between" seems to have a different meaning than in English, e.g. "between two and four" is equivalent to "exactly three". But according to the explanation of the example the meaning is "2, 3 or 4". Correct?
2. In the description of the "Set"-item it says that those items "begin" with [...]. Does the meaning of "begin" imply that there MUST be a continuation, i.e. that a "Set"-item must be at least two words long?
3. Similar the following: Does "ends in 's" imply that there must be at least one character in front of the "'s"?

RAJDEEP GUPTA: 2013-06-05 05:42:19

I agree. It was my fault. :)

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

@Wesley: What is your user account name in SPOJ forum? I can only PM you via the forum.

Wesley May: 2013-06-05 05:42:19

I'm the problem setter by the way if you have any questions. Feel free to PM me.

I guarantee you that there are no errors in the test data. This problem was used in an actual contest. A lot of people got WA because they didn't read the problem carefully. After explaining what they missed, they were all satisfied that the errors were *theirs*.

Last edit: 2013-06-04 02:44:35

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