ICPC ECNA 2016 I - Waif Until Dark

View as PDF

Submit solution

Points: 15
Time limit: 0.6s
Memory limit: 1G

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
ICPC East Central NA Regional Contest 2016, Problem I

"Waif Until Dark" is a daycare center specializing in children of households where both parents work during the day. In order to keep the little monsters ... that is, darlings ... occupied, the center has a set of toys that the kiddies can play with. Some of these toys belong to one of several categories – sports toys, musical toys, dolls, etc. In order to save wear and tear on these types of toys, the teachers allow only certain numbers of toys of each category to be used during playtime. Of course, kids being kids, not all of the toys are liked by everyone, so sometimes it's difficult to make sure every kid has a toy they like. Given all of these constraints, the CEO of Waif has come to you to write a little program to determine the maximum number of these monsters (let's be honest here) who can be satisfied.

Input Specification

Input starts with a line containing three integers n\ m\ p indicating the number of children, the number of toys and the number of toy categories (1 \le n,m \le 100, 0 \le p \le m). Both children and toys are numbered starting at 1. After this line are n lines of the form k\ i_1\ i_2 \dots i_k (1 \le k, i_1, i_2, \dots, i_k \le m) ; the j^{th} of these lines indicates that child j is willing to play with toys i_1 through i_k. Next are p lines of the form l\ t_1\ t_2 \dots t_l\ r (1 \le r \le l \le m, 1 \le t_1, t_2, \dots, t_l \le m); the j^{th} of these lines indicates that toys t_1 through t_l are in category j and that at most r of these toys can be used. Toys can be in at most one category and any toy not listed in these p lines is not in any toy category and all of them can be used. No toy number appears more than once on any line.

Output Specification

Display the maximum number of children that can be satisfied with a toy that they like.

Sample Input

4 3 1
2 1 2
2 1 2
1 3
1 3
2 1 2 1

Sample Output

Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported


  • 0
    ramjet_engine  commented on Dec. 3, 2016, 5:50 p.m.

    Any attempt to submit to this problem results in an internal error.

    • 0
      Kirito  commented on Dec. 3, 2016, 6:02 p.m.

      Issue has been fixed.