CERC '00 H - Hotline

View as PDF
Submit solution
Points: 25
Time limit: 0.6s
Memory limit: 64M
Problem type
ICPC Central European Regional Contest 2000, Problem H

Every customer sometimes needs help with new and unusual products. Therefore, hotline service is very important for every company. We need a single phone number where the customer can always find a friendly voice ready to help with anything. On the other hand, many people are needed to serve as hotline operators, and human resources are always very expensive. Moreover, it is not easy to pretend "friendly voice" at 4 am and explain to a drunken man that you are really unable to give him the number to House of Parliament. It was also found that some of the questions repeat very often and it is very annoying to answer them again and again.

ACM is a modern company, wanting to solve its hotline problem. They want to decrease the number of human operators by creating a complex software system that would be able to answer most common questions. The customer's voice is analysed by a special Voice Recognition Module (VRM) and converted to plain text. The text is then taken by an Artificial Automatic Adaptive Answering Algorithm (AAAAA). The most common questions are recognised and answered automatically. The replies are then converted to a sound by Text-to-Speech Module (TTS).

You are to write the AAAAA module. Because your algorithm should be adaptive, it has no explicit knowledge base. But it must be able to listen to sentences in English and remember the mentioned facts. Whenever a question is asked about such a fact, the system has to answer it properly. The VRM and TTS modules are already implemented, so the input and output of AAAAA will be in the text form.

Due to the incorrect reference solution that was provided, additional test cases have been provided. Data are provided by Ninjaclasher.

Input

There is a single positive integer T on the first line of input. It stands for the number of dialogues to follow. Each dialogue consists of zero or more lines, each of them containing one sentence: either statement or question. The statement ends with a dot character (.), the question ends with a question mark (?). No statement will appear more than once, however the questions can be repeated. There is one extra line after each dialogue. That line ends with an exclamation mark (!).

Sentences can contain words, spaces and punctuation characters (such as commas, colons, semicolons etc.). All words contain only letters of the English alphabet and are case-sensitive. That means the same word is always written the same way, usually in lowercase. Acronyms, names and some other words can begin with capital letters. For simplicity, all sentences begin with a lowercase letter. Only if the first word should be written with a capital, the sentence begins with a capital letter. There are no unneeded spaces between words. No line will have more than 100 characters. There will be at most 100 statements per test case.

Statements

Each statement has one of the following two forms (~ denotes a space):

subject ~ predicate[s] [ ~ object] .

subject ~ don't|doesn't ~ predicate [ ~ object].

The square brackets mark an optional part, the vertical line two possible variants. Subject is a single word, noun or pronoun in singular. Predicate is a verb (single word) denoting some activity. Object can be any text. Object does not contain any dots. Any pair "verb + object" determines unique activity. The same verb with different objects makes different independent activities, i.e. the different and independent meaning of the sentence. Sentence without any object can be considered as sentence with an empty object. The verb without an object has different and independent meaning than the same verb with any non-empty object.

The first variant of sentence denotes a positive statement. The word "predicate[s]" means verb that matches the subject of the sentence. If the subject is I or you, the verb has the same form as the infinitive. With any other subject, the letter s is appended at the end of the verb. Assume there are no irregular verbs.

The second variant is a negative statement. Verb don't or doesn't must also match the subject. The form don't is used with either I or you, doesn't is used in any other case.

A special generic subject everybody can be used. It means the activity holds for any subject. Other special subject is nobody. Such sentence also holds for any subject, but its meaning is negative. Both of these generic subjects can be used with the first variant only (without doesn't). The sentence nobody likes something is exactly equal to everybody doesn't like something, except the latter form will never occur in the input.

Questions

Each question has one of the following three forms:

  1. do|does ~ subject ~ predicate [ ~ object] ?
  2. who ~ predicates [ ~ object] ?
  3. what ~ do|does ~ subject ~ do ?

The word do|does always matches the subject (do I?, do you?, "does any other subject?"). In the second type of question, predicate always matches the word who, i.e. the s is always appended. Generic subjects cannot be used in questions.

Output

For each dialogue, your program must output the line Dialogue #D:, where D is the sequence number of dialogue, starting with 1. Then print exactly three lines for every question: the first line repeats the question, the second line contains the answer, and the third line is empty. Print nothing for statements. After each dialogue, print the same line with an exclamation mark that was in the input. Then print one extra empty line. Empty line contains a new-line character only.

The answer must be properly formatted to be accepted by a TTS module. Only the statements appearing in the input before the answer are used for the corresponding reply. If there is any contradiction among statements, the reply is always I am abroad.. If the question and statements consider the special subject you, it must be replaced with I in the answer. If the question considers special subject I, it must be replaced with you in the answer. The verb must always match the subject of the sentence. The exact form of the correct answer depends on the type of question.

1. does subject predicate [object] ?

If there is any positive statement about the mentioned subject (or generic subject everybody), predicate and object, the answer is: yes, ~ subject ~ predicate[s] [ ~ object] .

If there is any negative statement about the mentioned subject (or generic subject nobody), predicate and object, the answer is: no, ~ subject ~ don't|doesn't ~ predicate [ ~ object] .

Otherwise, the answer is: maybe.

Subject in the answer is always the same subject as the subject of the question.

2. who predicates [object] ?

If there is a positive statement considering any subject, the specified predicate and object, the answer is: subject ~ predicate[s] [ ~ object] .

If two or more subjects match the activity, replace the subject in the answer with an enumeration of all such subjects, in the same order as the corresponding statements have appeared in the input. Subjects are separated with comma and space, last two subjects are separated with the word and. If everybody belongs to the group of enumerated subjects, do not enumerate subjects, and print everybody only. If the enumeration contains at least two subjects, the predicate matches the plural subject (i.e. verb is without trailing s), otherwise it matches the only subject. subject1 , ~ subject2 ~ and ~ subject3 ~ predicate [ ~ object] .

If there is a negative statement considering the generic subject nobody, the specified predicate and object, the answer is: nobody ~ predicates [ ~ object] .

Otherwise, the answer is: I don't know.

3. what does subject do ?

If there are one or more sentences (both positive and negative) considering the specified subject (or a generic subject everybody or nobody), all verbs and objects from such sentences must be included in a reply in the same order as the corresponding sentences have appeared in the input. No verb-object pair can be included more than once (the eventual second appearance must be skipped). The verb-object pairs are separated by a comma followed by a space, the last verb is separated by a comma and the word and. Please note the comma is printed here although there was no comma when separating the subjects in the previous type of answer (see above). The negative answers have the same form as the statements, that means the verb don't or doesn't is used:

subject [ ~ don't|doesn't] ~ predicate1[s] [ ~ object1] ,

[ ~ don't|doesn't] ~ predicate2[s] [ ~ object2] ,

~ and [ ~ don't|doesn't] ~ predicate3[s] [ ~ object3] .

subject [ ~ don't|doesn't] ~ predicate1[s] [ ~ object1] ,

~ and [ ~ don't|doesn't] ~ predicate2[s] [ ~ object2] .

subject [ ~ don't|doesn't] ~ predicate[s] [ ~ object] .

Otherwise, the answer is: I don't know.

Sample Input

1
I like hotdogs.
nobody likes to work.
everybody smiles.
what do I do?
who smiles?
what do you do?
does Joe smile?
do I like to work?
everybody hurts sometimes.
who walks there?
Michal walks there.
who walks there?
what does Michal do?
do you understand?
nobody walks there.
do you understand now?
bye!

Sample Output

Dialogue #1:
what do I do?
you like hotdogs, don't like to work, and smile.

who smiles?
everybody smiles.

what do you do?
I don't like to work, and smile.

does Joe smile?
yes, Joe smiles.

do I like to work?
no, you don't like to work.

who walks there?
I don't know.

who walks there?
Michal walks there.

what does Michal do?
Michal doesn't like to work, smiles, hurts sometimes, and walks there.

do you understand?
maybe.

do you understand now?
I am abroad.

bye!
Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments


  • -4
    notveryimportant745  commented on May 13, 2020, 6:19 p.m.

    If there is one statement saying:

    I play video games.

    Then a question asking:

    do I play?

    What should the output be? And what about vice-versa? e.g.

    I play.

    and then

    do I play video games?

    • 4
      prophet  commented on May 15, 2020, 2:25 a.m.

      "The verb without an object has different and independent meaning than the same verb with any non-empty object."


  • -3
    noYou  commented on May 12, 2020, 12:52 a.m.

    Can we get non grammatically correct data? for example is I doesn't eat possible?


    • 5
      ManchurioX  commented on May 12, 2020, 1:09 a.m.

      I will never be used with doesn't

      The form "don't" is used with either "I" or "you", "doesn't" is used in any other case.


  • 2
    discoverMe  commented on May 3, 2019, 10:51 p.m. ← edit 5

    can "doesn't" or "don't" be a predicate

    2) and if inputted "subject doesn't predicate" and then asks question "who predicate" should it output "subject doesn't predicate"

    1. can you have the sentence "nobody doesn't predicate"

  • 3
    geese  commented on March 13, 2019, 4:08 a.m.

    Has the original reference solution been corrected?


  • 1
    Jeffmagma  commented on March 2, 2019, 11:52 p.m. ← edit 2

    subject1 , ~ subject2 ~ and ~ subject3 predicate [~ object].

    is this missing a ~ between subject3 and predicate?

    Sentences can contain words, spaces and punctuation characters (such as commas, colons, semicolons etc.)

    also, when are semicolons and colons used?


    • 1
      wleung_bvg  commented on March 3, 2019, 3:50 a.m.

      Yes, there should be a space. The semicolons and colons may appear in the sentence anywhere, but without breaking any of the rules. They should just be treated the same way as alphanumeric characters.


  • 2
    benito255  commented on Feb. 25, 2019, 5:22 p.m.

    I don't suppose someone can check to see why I'm getting a WA? It seems to give the correct output for the test data and I've thrown quite a few variations in for testing, but this is a hard one without any feedback :)

    Sorry in advance for the horrible code - still learning python!


    • 2
      wleung_bvg  commented on Feb. 25, 2019, 7:05 p.m. ← edit 2

      When answering the who question, you do not switch I to you and vice versa.


      • 2
        snowdozer  commented on March 8, 2019, 8:16 p.m. ← edited

        this comment hung me up for a while because I thought it referred to the generic subject "you" (everyone shouldn't swap I and you) rather than the direct subject "you" (benito255 doesn't swap I and you). seems kind of fitting considering the question lol


      • 1
        benito255  commented on Feb. 26, 2019, 12:30 a.m.

        Thanks so much! That was one of about 10 problems I eventually found with my code. Took some more thorough testing to get there in the end...


  • 0
    p1geon  commented on Feb. 25, 2019, 4:25 a.m.

    will "nobody" be used as a subject in a question


    • 1
      geese  commented on Feb. 25, 2019, 3:41 p.m.

      Generic subjects cannot be used in questions.


  • 2
    Jeffmagma  commented on Feb. 24, 2019, 10:27 p.m.

    wait is it a contradiction if they say everybody smiles. then nobody smiles.? or does the nobody smiles. overwrite the everybody smiles.?


    • 1
      d  commented on Feb. 24, 2019, 11:22 p.m.

      Yes.

      No, all statements are true at the same time.


      • 1
        Jeffmagma  commented on March 2, 2019, 9:18 p.m.

        So if they say Joe eats. then Joe doesn't eat. that's a contradiction too?


  • 4
    Zeyu  commented on Feb. 24, 2019, 12:15 p.m. ← edit 3

    If the subject is "nobody" or "everybody", do we check all the subjects or only their respective subject? Also, do we still have to print an extra empty line for the last dialogue?

    EDIT: Okay I somehow passed. Here are the answers to the questions I had above:

    • Only check their respective subject. If it's nobody or everybody it doesn't mean you check all the other people. (really late edit: it's stated that this case will never happen, oops!)
    • Always print an extra line in the end. Even if the example doesn't show the last line.

  • 2
    Jeffmagma  commented on Feb. 23, 2019, 10:36 p.m. ← edited

    is it possible for one predicate to have multiple objects in different statements? for example Joe likes cheese. then Joe likes tacos.

    also, what does bye! mean? it isn't stated anywhere that it indicates the end of a dialogue


    • 2
      Zeyu  commented on Feb. 24, 2019, 1:19 p.m.

      Yes, The same verb with different objects makes different independent activities. Also, the exclamatory mark of bye! indicates the dialogue's end.


      • 2
        Jeffmagma  commented on Feb. 24, 2019, 6:21 p.m.

        can you give some hints on what i'm doing wrong? do i have to use a better data structure?


        • 2
          Zeyu  commented on Feb. 24, 2019, 6:35 p.m.

          The issue with your TLE isn't what you think it is, reread how every dialogue ends in the input section :)


          • 2
            Jeffmagma  commented on Feb. 24, 2019, 9:59 p.m.

            ohhh ok, i'm dumb thanks