National Olympiad in Informatics, China, 2000

Day 1, Problem 3 - Mystery of the Lost City

The famous archaeologist professor Shi has found the ruins of an ancient city on the Yunmeng plateaus. What makes the professor happy is that the city, known as Ice-Peak City, contains 12 enormous stone slabs. The slabs contain information written in a particular text, which he decided to call the Ice-Peak texts. However when the professor tried to subsequently revisit the city using his map, he repeatedly failed.

Luckily, the professor had initially photographed the texts on the stone slabs. In order to uncover the mystery of the lost Ice-Peak City, the professor and his assistant Dr. Niu began analyzing the texts. They discovered that the Ice-Peak texts only contain declarative sentences of a fixed structure, along with nouns, verbs, and adjectives as the three types of words. Its grammar is very simple (the following is expressed in Backus-Naur Form):

    <article> ::= <sentence> { <sentence> }
   <sentence> ::= <declaration>
<declaration> ::= <noun-phrase> { <verb-phrase> <noun-phrase> } [ <verb-phrase> ]
<noun-phrase> ::= <noun> | [ <adjective> ] <noun-phrase>
<verb-phrase> ::= <verb> | [ <adjective> ] <verb-phrase>
       <word> ::= <noun> | <verb> | <adjective>

Note: Possible <noun>s, <verb>s, and <adjective>s will be given in a dictionary. "::=" indicates a definition. "|" denotes or. An expression in curly braces {} indicates that it may occur 0 or more times. An expression in square brackets [] indicates that it occur 0 or 1 times.

After analyzing large amounts of data, the duo have formulated an Ice-Peak dictionary. Coincidentally, due to the Ice-Peak language consisting of exactly 26 symbols, the symbols will be represented by the lowercase letters from a to z, for simplicity of the research process.

There does not exist any separator symbols or punctuation between adjacent words and adjacent sentences in Ice-Peak texts. This results in a very hard time for professor Shi and Dr. Niu when they are partitioning the words and sentences. That's when they came up with the idea of using a computer to help them. Assuming that you have accepted this job from them, your first task is to write a program which parses an Ice-Peak article into the fewest number of sentences as possible. Under this condition, the article must be partitioned into the fewest number of words as possible.

Input Format

The first line of input contains the number of words in the dictionary n (n ≤ 1000).
Line 2 to line n+1 each contains one word in the format α.mot, where α represents the type of the word (possibly n for noun, v for verb, or a for adjective), and mot is the word itself (no longer than 20 characters). Words with the same spelling but different types are considered different words; for instance, the words n.kick and v.kick in the sample input are different words.
Line n+2 contains the Ice-Peak text that must be partitioned, terminated by a period ".".
This text is guaranteed to follow the proper Ice-Peak text format, and will be made up of a finite number of sentences, where each sentence is made up of a finite number of words. The size of the text will not exceed 5KB.

Output Format

The output should consist of two lines, each containing one integer. The first line should contain the number of partitioned sentences. The second line should contain the number of partitioned words.

Sample Input

11
n.table
n.baleine
a.silly
n.snoopy
n.sillysnoopy
v.is
v.isnot
n.kick
v.kick
a.big
v.cry
sillysnoopyisnotbigtablebaleinekicksnoopysillycry.

Sample Output

2
9

Explanation

(For readability, the partitioned words below will be separated by spaces, and the types of words will follow them as superscripts. Each line contains a single sentence, followed by a period to denote the end of the sentence.) The corresponding partition for the sample output is:

sillysnoopyn isnotv biga tablen.
baleinen kickv snoopyn sillya cryv.

If the article was partitioned the following way:

sillya snoopyn isnotv biga tablen.
baleinen kickv snoopyn sillya cryv.

then there would still be two sentences, but the number of words would increase by 1, totaling 10 words. Clearly, partitioning should be done using the former method and not the latter.

All Submissions
Best Solutions

Point Value: 17 (partial)
Time Limit: 1.00s
Memory Limit: 64M
Added: May 06, 2014

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

Comments (Search)