alinieri

Se consideră modelul unui sistem solar format din $N$ planete care se rotesc în jurul unei stele $S$, în sens trigonometric. Traiectoriile planetelor se consideră circulare și de raze diferite, iar vitezele de rotație ale planetelor în jurul stelei sunt numere naturale și sunt exprimate în grade pe zi ($\degree$/zi).

Cerință

Cunoscând numărul de planete $N$ și vitezele lor de rotație $V_i$, $1 \leq i \leq N$, precum și două numere naturale $P$ și $Z$, să se determine numărul $A$ de alinieri a câte minimum $P$ planete, pe o dreaptă ce trece prin centrul stelei $S$, după trecerea celor $Z$ zile. Evoluția sistemului solar începe cu toate planetele așezate orizontal, în dreapta stelei $S$.

Spre exemplu, pentru $N=4$, $P=3$, $Z=365$ și $V = [20, 11, 8, 6]$, alinierea a minimum $3$ planete din cele $4$ se va face la finalul zilelor $60$, $90$, $120$, $180$, $240$, $270$, $300$, $360$. După $365$ de zile vor exista $A=8$ alinieri. În imaginea din dreapta se observă poziția planetelor la prima aliniere.
Figura 1 din enunțul original al problemei alinieri.Mărește schema ↗

Date de intrare

Fișierul de intrare alinieri.in conține pe prima linie, în această ordine, numerele naturale $N$, $P$ și $Z$, iar pe a doua linie, $N$ numere naturale $V_i$, $1 \leq i \leq N$ cu semnificația de mai sus. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire alinieri.out va conține pe prima linie numărul $A$, cu semnificația de mai sus.

Restricții și precizări

• $2 \leq P \leq N \leq 10^5$
• $1 \leq Z \leq 10^6$
• $1 \leq V_i \leq 10^3$, $1 \leq i \leq N$
• Pentru teste în valoare de $30$ de puncte, $1 \leq Z \leq 1\ 000$.
• Pentru teste în valoare de $30$ de puncte, $1 \leq N \leq 100$.
• Pentru teste în valoare de $30$ de puncte, $2 \leq P \leq 9$.
• Se vor lua în considerare doar alinierile de la sfârșitul fiecărei zile (ora 24:00), când planetele și-au încheiat parcursul zilnic.

Exemplul 1

alinieri.in

4 3 365
20 11 8 6

alinieri.out

8

Explicație

$N=4$, $P=3$, $Z=365$ și $V = [20, 11, 8, 6]$.

Prima aliniere a minimum $3$ planete dintre cele $4$ planete are loc după $60$ de zile (conform figurii de mai sus).

Evoluția celor $4$ planete este următoarea:

• planeta $1$ efectuează 3 rotații complete și încă $120\degree$;
• planeta $2$ efectuează o rotație completă și încă $300\degree$;
• planeta $3$ efectuează o rotație completă și încă $120\degree$;
• planeta $4$ efectuează exact o rotație.

Următoarele alinieri a minimum $3$ din cele $4$ planete au loc după $90$, $120$, $180$, $240$, $270$, $300$, $360$ de zile. Deci, în $365$ vor avea loc $8$ alinieri.

Exemplul 2

alinieri.in

7 3 2020
10 20 10 15 20 10 20

alinieri.out

3928

Explicație

$N=7$, $P=3$, $Z=2020$ și $V = [10, 20, 10, 15, 20, 10, 20]$.

În cele $2020$ de zile au avut loc $3928$ de alinieri a minimum $3$ planete din cele $7$ planete ce formează sistemul solar.

Exemplul 3

alinieri.in

6 3 658903
17 24 12 150 200 12

alinieri.out

58568

Explicație

$N=6$, $P=3$, $Z=658903$ și $V = [17, 24, 12, 150, 200, 12]$.

În cele $658903$ de zile au avut loc $58568$ de alinieri a minimum $3$ planete din cele $6$ planete ce formează sistemul solar.