ZOJ Problem Set - 3345
Xii is a very talented student who is interested in languages. By now she has learnt more than 10 computer languages and can use them to write powerful programs. But recently she was considering learning more human languages, so she picked Chinese, English, Japanese and German to learn.
Learning four foreign languages at the same time seemed unbelievable, but it was quite easy for our language genius Xii. It took only a few days for her to learn some basic sentence patterns and some frequently used words.
Following is the sentence patterns Xii has learnt.
Xii was happy to learn so many languages and she tried to write down some lines, although she might wrote wrong sentences or wrong words. Now you are given the vocabulary of Xii and some sentences she wrote down, you are to tell which languages they belong to.
First line is the number of test cases T (1 <= T <= 5).
Following are T cases. For each case, the first line is the number of words n and the number of sentences Xii wrote m (1 <= n <= 20, 1 <= m <= 20). The next n lines describe the n words. Each line is three parts separated by spaces. The first part is the language it belongs to, and it is one of the four languages above. The second part is the catalog, and it belongs to what appear in the sentence patterns. The third part is the word which composed of no less than 1 and no more than 10 English letters. Note that a word may belong to different languages or belong to different catalogs of same language. Following m lines are what she wrote down. A sentence will not be more than 20 words and will not be longer than 30.
For each case, first print a line "Case #?:" where ? is the case number starting from 1.
Then print what language each sentence belongs to. If the sentence does not fit to any sentence patterns, print a line "I don't know.". A sentence will belong to at most one sentence pattern.
2 10 4 German [n] Apfel Japanese [adj] suki Chinese [n] ren English [vt] drink Chinese [pn] wo English [n] milk Japanese [pn] watashi Japanese [pn] anta Japanese [n] tensai English [pn] They watashi ha tensai da Ich bin tensai They drink milk wo shi ran 1 1 German [n] Apfel Ich habe ein Apfel
Case #1: Japanese I don't know. English I don't know. Case #2: German
Author: ZHUANG, Junyuan
Contest: ZOJ Monthly, June 2010