CCO '14 P3 - Werewolf

View as PDF

Submit solution

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
Canadian Computing Competition: 2014 Stage 2, Day 1, Problem 3

As they usually do, N robots are playing the game of Werewolf, and the robots are numbered with integers from 1 to N. Exactly W 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 A to accuse or defend a robot B, then A < B.

You will be given all the accusations and defenses between N robots where there are exactly W 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):

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

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

  • A a b indicates that robot a accused robot b of being a werewolf;
  • D a b indicates that robot a defended robot b.

You may assume that for 20% of the marks for this problem, N \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 + 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 1 is a werewolf, then robot 2 must also be, which is too many werewolves! The only possibility is that robot 2 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 1 or robot 2 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 1 is a werewolf, which implies robot 2 is a civilian and robot 3 is a werewolf as well, or robot 1 is a civilian (which allows robot 2 and 3 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