CCO '14 P3 - Werewolf

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 1.0s
Memory limit: 256M

Problem type
Canadian Computing Competition: 2014 Stage 2, Day 1, Problem 3

As they usually do, NN robots are playing the game of Werewolf, and the robots are numbered with integers from 11 to NN. Exactly WW of these robots are werewolves, and the remainder are civilians. Though the game of Werewolf involves various aspects, we will focus on a single discussion phase of the game.

Robots accuse other robots of being werewolves and defend other robots by vouching for their innocence.

The werewolves know each other's identities and:

  • A werewolf never accuses another werewolf;
  • Any robot that a werewolf defends is another werewolf.

Civilians may accuse or defend either type of robot.

Additional constraints to make our task a bit easier:

  • No robot is both accused and defended.
  • No robot is accused or defended more than once.
  • For a robot AA to accuse or defend a robot BB, then A < BA < B.

You will be given all the accusations and defenses between NN robots where there are exactly WW werewolves. A role assignment identifies each of the robots as either werewolf or civilian. Your goal is to figure out how many role assignments satisfy all the above constraints.

Input Specification

The first line contains three numbers (each separated by one space):

  • NN (1 \le N \le 200)(1 \le N \le 200), the number of robots, followed by
  • WW (0 \le W \le N)(0 \le W \le N), the number of werewolves, followed by
  • MM (0 \le M \le N)(0 \le M \le N), the number of accusations/defenses.

The next MM lines give the accusations and defenses. Each of these lines will be one of the following two forms:

  • AA aa bb indicates that robot aa accused robot bb of being a werewolf;
  • DD aa bb indicates that robot aa defended robot bb.

You may assume that for 20% of the marks for this problem, N \le 20N \le 20.

Output Specification

Output the number of role assignments that are consistent with the given information. Since this number may be very large, you must output this answer modulo 10^9 + 710^9 + 7.

Sample Input 1

2 1 1
D 1 2

Output for Sample Input 1

1

Explanation of Output for Sample Input 1

If robot 11 is a werewolf, then robot 22 must also be, which is too many werewolves! The only possibility is that robot 22 is the sole werewolf.

Sample Input 2

2 1 0

Output for Sample Input 2

2

Explanation of Output for Sample Input 2

With no information, either robot 11 or robot 22 could have been a werewolf.

Sample Input 3

3 2 2
A 1 2
D 1 3

Output for Sample Input 3

2

Explanation of Output for Sample Input 3

Either robot 11 is a werewolf, which implies robot 22 is a civilian and robot 33 is a werewolf as well, or robot 11 is a civilian (which allows robot 22 and 33 to both be werewolves).


Comments


  • -6
    Roronoa_Zoro1540  commented on Feb. 9, 2020, 8:52 p.m. edited

    This comment is hidden due to too much negative feedback. Click here to view it.


  • 4
    geese  commented on March 23, 2018, 10:56 a.m.

    Output specification

    you must output this answer "module" 109+7

    Do you mean modulo?


    • 5
      Kirito  commented on March 23, 2018, 6:22 p.m.

      Fixed. Thank you for pointing that out!


  • 1
    fifiman  commented on March 12, 2015, 5:06 p.m.

    Sample input 2 is missing and explanation of sample input 1