The Voight-Kampff test P24695


Statement
 

pdf   zip

html

Blade Runner Rick Deckard is identifying replicants at Tyrell Corporation. Rick distinguishes who is a replicant and who is human using a Voight-Kampff machine, which is a sort of lie detector that measures contractions of the iris muscle and also the degree of the empathic response of individuals through careful questions.

How complicated…Rick is so tired of it! Therefore, he will just pretend that he is making the Voight-Kampff test, while in fact he will only record some answers. Rick makes these assumptions: all humans and replicants know who is what (because humans at Tyrell Corporation are genetic designers, and replicants are smarter than Rick), humans always tell the truth, and replicants always lie.






For instance, consider the first example of the sample input, where Tyrell claims that Rachael is a replicant, and Rachael claims that Tyrell is a replicant. Under Rick’s assumptions, there are exactly two situations consistent with these two claims: (1) Tyrell is human and Rachael is a replicant, and (2) Tyrell is a replicant and Rachael is human.

Input

Input consists of several cases. Every case begins with a number 2 ≤ n ≤ 1000, followed by n different names, and by a number m ≥ 0. Follow m lines, each with an answer following exactly the format of the sample input. No individual speaks about (him/her/it)-self.

Output

For every case, print its number starting at one, and the number of situations consistent with the answers recorded and Rick’s assumptions. This number will always be less than 231.

Public test cases
  • Input

    2 Tyrell Rachael 2
    Tyrell : Rachael is a replicant
    Rachael : Tyrell is a replicant
    
    2 Tyrell Rachael 2
    Tyrell : Rachael is a replicant
    Rachael : Tyrell is human
    
    2 Tyrell Rachael 2
    Rachael : Tyrell is human
    Rachael : Tyrell is a replicant
    
    4 Tyrell Rachael Sebastian Pris 5
    Pris : Rachael is human
    Tyrell : Rachael is a replicant
    Rachael : Tyrell is a replicant
    Pris : Tyrell is a replicant
    Rachael : Pris is human
    

    Output

    Case 1: 2
    Case 2: 0
    Case 3: 0
    Case 4: 4
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Sisè Concurs de Programació de la UPC - Semifinal
    Date
    2008-06-28