Problem 1420: Showroom

Un showroom din Strasbourg comercializează o gamă foarte mare de modele de autoturisme, aşezate pe $n$ linii. Pe câte o linie se găsesc numai modele de autoturisme comercializate de acelaşi dealer. Un dealer poate avea modele pe mai multe linii. Parlamentul European doreşte să-şi înoiască parcul auto şi trimite responsabilul cu activitatea de transport la showroom pentru a se informa cu privire la variantele pe care le are pentru rezolvarea acestei probleme de achiziţie. Responsabilul trebuie să aleagă de la primul dealer $f_1$ modele, de la al doilea dealer $f_2$ modele, etc.

Şirul de numere $f_1, f_2, f_3, \ldots$ reprezintă termenii $mod \ k$ ai unei progresii aritmetice cu primul termen $a$ şi raţia $r$ . Dacă valoarea din şirul de numere este mai mare decât numărul de modele al dealerului corespunzător, atunci responsabilul nu mai alege nici un model al dealerului. Primul dealer este cel care are modelele pe prima linie şi, eventual, pe alte linii care urmează primei linii (dar nu neapărat consecutive!), al doilea dealer este cel care are modelele pe prima linie ce conţine modele diferite de cele ale primului dealer etc.

Cerinţă

Să se scrie un program care determină:

$a)$ Numărul de dealeri prezenţi în showroom;

$b)$ Numărul de modalităţi de achiziţie al modelelor de către Parlamentul European, $mod \ 9 \ 001$ .

Date de intrare

Fişierul de intrare showroom.in conţine pe prima linie numerele $n,a,r,k$ separate prin exact un spaţiu, cu semnificaţia de mai sus, iar pe următoarele $n$ linii se află denumirile modelelor din enunţ, separate prin unul sau mai multe spaţii.

Fiecare linie se termină cu caracterul sfârşit de linie.

Date de ieşire

Fişierul de ieşire showroom.out va conţine pe prima linie numărul cerut la subpunctul $a)$ , iar pe a doua linie numărul cerut la subpunctul $b)$ .

Restricţii şi precizări

$1 \leq n \leq 500$
$1 \leq a, r, k \leq 10 \ 000$
Denumirea unui model are cel mult $20$ de litere mici şi/sau cifre
Pe o linie sunt cel mult $100$ de denumiri de modele şi nu pot exista mai mult de $10$ spaţii între două modele
Pot exista linii cu numerele de ordine $i_1, i_2, \ldots , i_p$ cu modele ale aceluiaş dealer, astfel încât perechile de linii $(i_1, i_2) , \ldots ,(i_{p-1}, i_p)$ au cel puțin un model de mașină în comun
Pentru rezolvarea corectă a fiecarei cerinţe se acordă $50$ % din punctaj
Acordarea punctajului pentru a doua cerință se face numai dacă în fișierul de ieșire există un răspuns pentru prima cerință, indiferent de corectitudinea acestuia
Pentru $60$ % din teste se garantează că valoarea $k$ este mai mică sau egală decât $10$

Exemplu

showroom.in

6 1 2 3
logan duster logan
peugeot207 peugeot307
sandero sandero
opelcorsa opelastra opelcorsa
peugeot207
sandero duster

showroom.out

3
3

Explicație

La showroom sunt $3$ dealeri.

Dealerul $1$ : logan, duster, sandero.

Dealerul $2$ : peugeot207, peugeot307.

Dealerul $3$ : opelcorsa, opelastra.

Primii trei termeni din progresia aritmetică sunt $1, 3, 5$ . $f_1=1 \ mod \ 3 = 1$ ; $f_2 = 3 \ mod \ 3 = 0$ ; $f_3 = 5 \ mod \ 3 = 2$ .

Modalităţile de achiziţie ale modelelor de la dealerul $1$ , a niciunui model de la dealerul $2$ şi a două modele de la dealerul $3$ sunt următoarele:

logan, opelcorsa, opelastra;
duster, opelcorsa, opelastra;
sandero, opelcorsa, opelastra.

Showroom