University of Toronto ACM-ICPC Tryouts 2012

D: Diablo Bot

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 preqrequisite 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. 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 ≤ N ≤ 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

Line 1: 1 integer, N
Next N lines: The name of the ith item, for i = 1..N

Output

N lines: The type of the ith 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

Sample Input

7
Somebody's Something of Whatever
stone of jordan
Wirt's Leg
FLAMING TURNIP
Damaged Goods
Sword
Fish shaped volatile organic compounds

Sample Output

Set
Magic
Set
Not sure, take anyways
Normal
Normal
Normal

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.

All Submissions
Best Solutions

Point Value: 15
Time Limit: 5.00s
Memory Limit: 64M
Added: Oct 02, 2012
Author: wjomlex

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Right now, I’m trying to submit my Python code. However, it seems to give a RunTime error. However, there are no runtime errors on the two IDEs that I’ve tried. Does anyone have any insight? Or is there an error in my code I haven’t stumbled upon?

you are not getting an runtime error, you are getting WA or wrong answer, meaning that your program does not produce the correct output

Oh, sorry for misunderstanding that.

Damn, that wording was tricky.

Would [i]'s[/i] on its own count as a set item?

Do exactly what the problem says.

Why is this problem worth 15 points?? Is string processing really difficult, or is there something I missed? I almost feel like I'm walking into a trap reading this question.

This question is somewhat tricky, yet I am inclined to agree with you that it is a touch overvalued. Personally I would decrease it to 10 points, but I don't want to step on anybody's toes... so for now, consider this as just a source of 5 free points. =]

Can someone please check my code and alert me (if possible and reasonable) of any mistakes? I have been trying to cover all of the cases, but am apparently still missing something. 

If you want other people to read your code, I strongly suggest indenting it properly.

Not algorithm related, but I suggest you read up about:
- continue
- List<> / ArrayList<>

Furthermore, we explicitly recommend against saving and then printing output at the end.

In what case would something be classified as rare? The only properties of rare is that is has 2 words in its name but so does magic.

I recommend a careful reading of the problem.

Can you explain? I've reread this problem so many times and I still cannot see where an item would be classified only as rare. Rare items only have 2 words and magic items have names between two and four word long. That means rare items could always be magic items. 

The problem statement contains all information necessary for solving it.

Wow that wording is so snake >.< Thanks for the help!

There are indeed snakes involved =D

Nothing is explained in this program well...nothing is detailed in the program...

Do you have any particular questions?

I cant understand when it would be Rare???

Cant a single person answer when it is RARE???

No, because reading problem statements carefully is an important skill to cultivate on one's own.

Gotta say, after struggling with this one for a couple of days, that writing clearly defined problem statements is also an important skill, and this particular problem suffers from a lack of well-defined use cases. In the absence of a single example of an item that is unambiguously Rare, I've had to conclude there's no such thing, and yet, I continue to get WA'd.

Is it not possible to be provided with a test case that should return Rare?

Actually, the case where an item is Rare is clearly defined. Providing a test case would defeat the purpose of having a problem such as this.

In other words, the problem is meant to be deliberately vague in an attempt to artificially inflate the difficulty. Thanks for clearing that up.

The description of item types is as precise as it needs to be without giving extraneous information. Perhaps you can say that not enough samples exist to spoonfeed you the answer, but it is definitely unfair to call the description vague. As far as I can see, none of the individual statements made in the description are unclear (I challenge you to find one that is). From these statements, it is definitely possible to deduce the trick to the solution. You really just need to think harder. Once you get it, you will agree with the rest of us.

Is the categories case sensitive? 
eg. is "Somebody'S Something of Whatever" still a valid set item and is "stone OF Jordan" a valid magic item? Same for "damaged goods".

This is answered in the problem statement.

I think I understand the trick behind the problem, but I am still getting the wrong answer when putting my code through the judge. Could someone please tell me what I am doing wrong?

According to a few of your most recent submissions, it would appear that you do not understand the trick behind the problem.