ACM U of T Tryouts C2 D - Diablo Bot

View as PDF
Submit solution
Points: 7 (partial)
Time limit: 2.5s
Memory limit: 64M
Author:
wjomlex
Problem type
University of Toronto ACM-ICPC Tryouts 2012

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. 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 \le N \le 1\,000) 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 Specification

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

Output Specification

N lines: The type of the ith item (one of Normal, Set, Magic, or Rare), or Not sure, take anyways if the item's type cannot be determined, but is known not to be Normal, for i = 1 \dots 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.

Comments


  • 0
    sweting  commented on Oct. 22, 2023, 12:17 a.m.

    Stuck? Focus on these words:

    If, and only if


  • 2
    tsumikimikanfan2  commented on Nov. 15, 2022, 8:36 a.m. ← edited

    wjomlex i am going to find you


  • 1
    throwawayassignment  commented on July 30, 2021, 5:16 a.m.

    Got a Zod Rune doe?


  • 1
    maxcruickshanks  commented on May 13, 2021, 3:54 a.m.

    Since the original data were weak, 9 more cases were added to the original batch, now worth a total of 100 marks.


    • 4
      wjomlex  commented on May 15, 2021, 10:58 p.m. ← edited

      I'm the original author of this problem, so I'm interested in the newly-added cases. Can you email them to me?


  • 0
    dxke02  commented on Dec. 3, 2020, 5:13 p.m. ← edited

    NVM


    • 0
      Kirito  commented on Dec. 4, 2020, 1:15 a.m.

      Reread the problem more carefully, there is indeed a scenario where you output rare.


      • 1
        Badmode  commented on Oct. 2, 2021, 7:59 p.m.

        After rereading multiple times, I still can't think of a scenario where the correct answer would be to output rare. Can some please comment a scenario where you would output rare?