/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 8 点
注意
この問題に対する言及は、2021/4/24 18:00 JST まで禁止されています。言及がなされた場合、賠償が請求される可能性があります。 試験後に総合得点や認定級を公表するのは構いませんが、どの問題が解けたかなどの情報は発信しないようにお願いします。
問題文
ある会社は N 種類の携帯電話を販売しています。これらの機種は機種 1 から機種 N まで番号づけられています。
また、携帯電話の周波数帯が M 個あり、周波数帯 1 から周波数帯 M まで番号づけられています。
機種 i の携帯電話は周波数帯 A_{i, 1}, A_{i, 2}, A_{i, 3}, \dots, A_{i, K_i} の K_i 個の周波数帯のみに対応しています。
あなたはこの会社の携帯電話のうち以下の条件を満たすものから 1 つ選んで買うことに決めました。
- 周波数帯 B_1, B_2, B_3, \dots, B_P の P 個の周波数帯のうち Q 個以上に対応している
あなたの買う携帯電話の候補となる機種の数を出力してください。
制約
- 1 \le N \le 50
- 1 \le M \le 50
- 1 \le K_i \le M
- 1 \le A_{i, j} \le M
- j \neq k ならば A_{i, j} \neq A_{i, k}
- 1 \le Q \le P \le M
- 1 \le B_i \le M
- i \neq j ならば B_i \neq B_j
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M
K_1 A_{1, 1} A_{1, 2} A_{1, 3} \dots A_{1, K_1}
K_2 A_{2, 1} A_{2, 2} A_{2, 3} \dots A_{2, K_2}
K_3 A_{3, 1} A_{3, 2} A_{3, 3} \dots A_{3, K_3}
\hspace{67pt} \vdots
K_N A_{N, 1} A_{N, 2} A_{N, 3} \dots A_{N, K_N}
P Q
B_1 B_2 B_3 \dots B_P
出力
答えを出力せよ。
入力例 1
4 4 1 4 2 3 1 3 2 1 3 2 2 4 2 1 2 4
出力例 1
3
それぞれの機種が対応している周波数は以下の通りです。
- 機種 1 : 周波数帯 4
- 機種 2 : 周波数帯 1, 3
- 機種 3 : 周波数帯 1, 2, 3
- 機種 4 : 周波数帯 2, 4
周波数帯 2, 4 のうち 1 個以上に対応している機種は、機種 1, 3, 4 です。
入力例 2
4 4 3 2 3 4 1 2 2 1 3 4 1 2 3 4 3 1 1 3 4
出力例 2
3
機種 1, 3, 4 が条件を満たします。
入力例 3
1 2 1 1 1 1 2
出力例 3
0
1 つも条件を満たす機種がない場合もあります。
Score : 8 points
Warning
Do not make any mention of this problem until April 24, 2021, 6:00 p.m. JST. In case of violation, compensation may be demanded. After the examination, you can reveal your total score and grade to others, but nothing more (for example, which problems you solved).
Problem Statement
A company sells N types of cellphones, called Type 1 through Type N.
Also, there are M frequency bands used for cellular networks, called Band 1 through Band M.
A cellphone of Type i can only use K_i of those bands: Bands A_{i, 1}, A_{i, 2}, A_{i, 3}, \dots, A_{i, K_i}.
You will buy a cellphone by this company that satisfies the following condition:
- The cellphone can use Q or more of the following P bands: Bands B_1, B_2, B_3, \dots, B_P.
Print the number of types of such cellphones.
Constraints
- 1 \le N \le 50
- 1 \le M \le 50
- 1 \le K_i \le M
- 1 \le A_{i, j} \le M
- A_{i, j} \neq A_{i, k} for j \neq k
- 1 \le Q \le P \le M
- 1 \le B_i \le M
- B_i \neq B_j for i \neq j
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M
K_1 A_{1, 1} A_{1, 2} A_{1, 3} \dots A_{1, K_1}
K_2 A_{2, 1} A_{2, 2} A_{2, 3} \dots A_{2, K_2}
K_3 A_{3, 1} A_{3, 2} A_{3, 3} \dots A_{3, K_3}
\hspace{67pt} \vdots
K_N A_{N, 1} A_{N, 2} A_{N, 3} \dots A_{N, K_N}
P Q
B_1 B_2 B_3 \dots B_P
Output
Print the answer.
Sample Input 1
4 4 1 4 2 3 1 3 2 1 3 2 2 4 2 1 2 4
Sample Output 1
3
Each type of cellphone can use the following bands:
- Type 1: Bands 4
- Type 2: Bands 1, 3
- Type 3: Bands 1, 2, 3
- Type 4: Bands 2, 4
The types that can use one or more of Bands 2, 4 are Types 1, 3, 4.
Sample Input 2
4 4 3 2 3 4 1 2 2 1 3 4 1 2 3 4 3 1 1 3 4
Sample Output 2
3
Types 1, 3, 4 are desirable.
Sample Input 3
1 2 1 1 1 1 2
Sample Output 3
0
There can be no desirable types.