Coloma, the cosmic shepperd dog P49965


Statement
 

pdf   zip

html

In a nutshell, Nofre Caps i Grany is a complete loser. He is unable to deal even with the simplest day-to-day situations, and it is a true miracle that he has managed to stay alive for as long as he has—that is, 12 years of age, out of which he spent five in the cradle…

However, and unbeknownst to him, the compendium of his misfortunes will become the foundational book of a 25th century neo-epicurean revival cult hundreds of years after the collapse of our current society, and the founders of such organization decide to send back in time one of their most advanced zooids to ensure that he can live up to the point where enough of his deeds (for lack of a better work) have been collected that they can justify a high enough price for the sale of their book and keep a sizable profit.

This is how Coloma, the cosmic shepperd dog, travelled through space-time and landed in our present time. She brought her supply of advanced gadgets and possesses an advanced AI to solve Nofre’s problems with them. The implementation uses the most bleeding edge technology of the future: a large set of rules (neural networks will turn out to be a 21st century fad…). Coloma knows about thousands of objects, their relationships, and what they do to each other. With that knowledge, she can always find all the objects she can use to get Nofre out of the problems he draws onto himself as a huge catastrophe magnet.

(The problem begins here )

Input

Input consists of several cases, each starting with the number of facts 1 ≤ n ≤ 1000 in Coloma’s database and the number of queries 1 ≤ m ≤ 25000 she’ll make to it.

Then come n triplets o1 v o2, with o1 and o2 being the names of objects, and v being a verb. They express that the object o1 can be used to v the object o2. The special verb “is” expresses that o1 is a subtype of o2, and hence all the actions that apply to o2 (both as a subject and as an object) also apply to o1. Each object o1 can only be a direct subtype of a single other o2. The subtype relationship is transitive and does not have cycles.

Finally, come m queries ‘?’ v o2, meaning: What objects can v the object o2? The verb v will never be “is” in this case.

All the words in this problem consist of a sequence of at most 20 alphabetic and underscore characters.

Output

For each query, print a line with the most general object she can use to solve the problem—meaning the one which is not a subtype of any other. If multiple such objects exist, print all of them in alphabetical order. If Coloma’s AI does not contain information of any object to perform the action, print instead “<RIP>”. Print a line with 10 dashes at the end of each case.

Observation

The expected solution does not use any sophisticated algorithm or data structure.

Public test cases

  • Input

    1 1
Key opens Door
? opens Door

3 2
Key opens Door
Gold_key opens Door
Gold_key is Key
? opens Door
? opens Key

3 4
Door is Wooden_object
Key opens Door
Axe opens Wooden_object
? opens Door
? opens Wooden_object
? closes Door
? opens Window

5 1
Gold_key opens Door
Big_red_gold_key is Red_gold_key
Red_gold_key is Gold_key
Gold_key is Key
Big_red_gold_key opens Door
? opens Door

    Output

    Key
----------
Key
<RIP>
----------
Axe Key
Axe
<RIP>
<RIP>
----------
Gold_key
----------
    • Information
    Author
    Edgar Gonzalez
    Language
    English
    Official solutions
    C++
    User solutions
    C++