codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

234D.md (3714B)


      1 Source: https://codeforces.com/problemset/problem/234/D
      2 
      3 D. Cinema
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 input.txt
     16 
     17 output
     18 
     19 output.txt
     20 
     21 Overall there are *m* actors in Berland. Each actor has a personal identifier — an integer from 1 to *m* (distinct actors have distinct identifiers). Vasya likes to watch Berland movies with Berland actors, and he has *k* favorite actors. He watched the movie trailers for the next month and wrote the following information for every movie: the movie title, the number of actors who starred in it, and the identifiers of these actors. Besides, he managed to copy the movie titles and how many actors starred there, but he didn't manage to write down the identifiers of some actors. Vasya looks at his records and wonders which movies may be his favourite, and which ones may not be. Once Vasya learns the exact cast of all movies, his favorite movies will be determined as follows: a movie becomes favorite movie, if no other movie from Vasya's list has more favorite actors.
     22 
     23 Help the boy to determine the following for each movie:
     24 
     25 * whether it surely will be his favourite movie;
     26 * whether it surely won't be his favourite movie;
     27 * can either be favourite or not.
     28 
     29 Input
     30 
     31 The first line of the input contains two integers *m* and *k* (1 ≤ *m* ≤ 100, 1 ≤ *k* ≤ *m*) — the number of actors in Berland and the number of Vasya's favourite actors.
     32 
     33 The second line contains *k* distinct integers *a**i* (1 ≤ *a**i* ≤ *m*) — the identifiers of Vasya's favourite actors.
     34 
     35 The third line contains a single integer *n* (1 ≤ *n* ≤ 100) — the number of movies in Vasya's list.
     36 
     37 Then follow *n* blocks of lines, each block contains a movie's description. The *i*-th movie's description contains three lines:
     38 
     39 * the first line contains string *s**i* (*s**i* consists of lowercase English letters and can have the length of from 1 to 10 characters, inclusive) — the movie's title,
     40 * the second line contains a non-negative integer *d**i* (1 ≤ *d**i* ≤ *m*) — the number of actors who starred in this movie,
     41 * the third line has *d**i* integers *b**i*, *j* (0 ≤ *b**i*, *j* ≤ *m*) — the identifiers of the actors who star in this movie. If *b**i*, *j* = 0, than Vasya doesn't remember the identifier of the *j*-th actor. It is guaranteed that the list of actors for a movie doesn't contain the same actors.
     42 
     43 All movies have distinct names. The numbers on the lines are separated by single spaces.
     44 
     45 Output
     46 
     47 Print *n* lines in the output. In the *i*-th line print:
     48 
     49 * 0, if the *i*-th movie will surely be the favourite;
     50 * 1, if the *i*-th movie won't surely be the favourite;
     51 * 2, if the *i*-th movie can either be favourite, or not favourite.
     52 
     53 Examples
     54 
     55 Input
     56 
     57 ```
     58 5 3  
     59 1 2 3  
     60 6  
     61 firstfilm  
     62 3  
     63 0 0 0  
     64 secondfilm  
     65 4  
     66 0 0 4 5  
     67 thirdfilm  
     68 1  
     69 2  
     70 fourthfilm  
     71 1  
     72 5  
     73 fifthfilm  
     74 1  
     75 4  
     76 sixthfilm  
     77 2  
     78 1 0
     79 ```
     80 
     81 Output
     82 
     83 ```
     84 2  
     85 2  
     86 1  
     87 1  
     88 1  
     89 2
     90 ```
     91 
     92 Input
     93 
     94 ```
     95 5 3  
     96 1 3 5  
     97 4  
     98 jumanji  
     99 3  
    100 0 0 0  
    101 theeagle  
    102 5  
    103 1 2 3 4 0  
    104 matrix  
    105 3  
    106 2 4 0  
    107 sourcecode  
    108 2  
    109 2 4
    110 ```
    111 
    112 Output
    113 
    114 ```
    115 2  
    116 0  
    117 1  
    118 1
    119 ```
    120 
    121 Note
    122 
    123 Note to the second sample:
    124 
    125 * Movie jumanji can theoretically have from 1 to 3 Vasya's favourite actors.
    126 * Movie theeagle has all three favourite actors, as the actor Vasya failed to remember, can only have identifier 5.
    127 * Movie matrix can have exactly one favourite actor.
    128 * Movie sourcecode doesn't have any favourite actors.
    129 
    130 Thus, movie theeagle will surely be favourite, movies matrix and sourcecode won't surely be favourite, and movie jumanji can be either favourite (if it has all three favourite actors), or not favourite.