Rezolvare PBinfo #4414

La o tragere loto expres specială se extrag M numere distincte din mulţimea {1, 2, 3, ..., 49}. O persoană care joacă la acest joc scrie pe bilet K numere distincte dintre cele 49 posibile. Categoriile de câştig sunt următoarele în ordine descrescătoare după valoarea câștigului (categoria 1 este cea mai valoroasă):

• categoria 1: K numere scrise pe bilet din primele K extrase oficial;
• categoria 2: K numere scrise din toate cele M extrase oficial;
• categoria 3: K-1 numere scrise din primele K-1 extrase oficial;
• categoria 4: K-1 numere scrise din primele K extrase oficial;
• categoria 5: K-1 numere scrise din toate cele M extrase oficial;
• categoria 6: K-2 numere scrise din toate cele M extrase oficial.

La tragere au cumpărat bilete J jucători. Un jucător câștigă la cea mai valoroasă categorie la care se încadrează.

Cerința

Să se scrie un program care să determine:

• Numărul de jucători câștigători pentru o categorie specificată C de câștig. Categoriile sunt numerotate {1, 2, ..., 6, 7}. Categoria 7 este destinată necâștigătorilor.
• Numerele care sunt alese de numărul maxim de jucători, scrise în ordine crescătoare.

Date de intrare

Fişierul de intrare loto.in conţine pe prima linie cerința (1 sau 2). Linia a doua conține numerele M K C separate prin câte un spaţiu. Linia a treia conţine, în ordinea în care au fost extrase, cele M numere extrase oficial, separate prin câte un spaţiu. Linia a patra conţine un număr natural J, reprezentând numărul de jucători, iar fiecare dintre următoarele J linii conține câte K numere naturale, în ordinea în care au fost jucate, reprezentând numerele alese și scrise pe bilet de cele J persoane.

Date de ieșire

Pentru cerința 1 fişierul de ieşire loto.out va conţine pe prima linie un număr natural, reprezentând numărul de câștigători pentru categoria de câştig C.
Pentru cerința 2 fişierul de ieşire loto.out va conţine pe prima linie numerele alese de numărul maxim de jucători, scrise în ordine crescătoare, separate prin câte un spațiu.

Restricții și precizări

• 1 ≤ M ≤ 49
• 5 ≤ K ≤ M
• 1 ≤ C ≤ 7
• 1 ≤ J ≤ 1000
• Pentru cerința 1 se acordă 70 puncte, iar pentru cerința 2 se acordă 30 puncte
• Pentru 15 puncte, 1 ≤ J ≤ 10
• Pentru 30 puncte, 11 ≤ J ≤ 100
• Pentru 55 puncte, 101 ≤ J ≤ 1000

Exemplul 1:

loto.in

1
6 5 1
1 2 3 4 5 6
1
5 4 3 2 1

loto.out

1

Explicație

Cerința 1. La extragerea oficială s-au extras 6 numere. Jucătorii pot completa 5 numere. Numerele extrase oficial sunt, în ordine, 1 2 3 4 5 6. Există un singur jucător. Acesta a scris pe bilet numerele 5 4 3 2 1. Persoana care a jucat a câștigat la categoria 1 deoarece a scris primele 5 numere extrase oficial.

Exemplul 2:

loto.in

1
6 5 4
1 2 3 4 5 6
2
9 1 5 3 2
3 1 5 2 4

loto.out

1

Explicație

Cerința 1. Există 2 jucători. Unul dintre jucători a câștigat la categoria 1 și unul a câștigat la categoria 4. Se cere numărul de câștigători la categoria 4, deci 1.

Exemplul 3:

loto.in

1
6 5 7
1 2 3 4 5 6
3
2 33 7 8 19
21 3 47 8 29
12 32 17 8 39

loto.out

3

Explicație

Cerința 1. Există 3 jucători. Nici unul dintre cei care au jucat nu a câștigat la nici o categorie.

Exemplul 4:

loto.in

2
6 5 4
1 2 3 4 5 6
2
9 1 5 3 2
3 1 5 2 4

loto.out

1 2 3 5

Explicație

Cerința 2. Numerele 1 2 3 5 au fost scrise de ambele persoane, deci numărul maxim de jucători este 2.