National Olympiad in Informatics, China, 2000
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 occurs 0 or more
times. An expression in square brackets []
indicates that it occurs 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 Specification
The first line of input contains the number of words in the dictionary
.
Line 2 to line 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 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 5 KB.
Output Specification
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.
Problem translated to English by .
Comments