Rezolvare PBinfo #3443

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 (⁰/zi).

Cerința

Cunoscând numărul de planete N și vitezele lor de rotație Vi, 1≤i≤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.

Exemplu

Pentru N=4, P=3, Z=365 și V1-4=[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.

Poziția planetelor la prima aliniere.

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 Vi, 1≤i≤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 ≤ P ≤ N ≤ 105
• 1 ≤ Z ≤ 106
• 1 ≤ Vi ≤ 103, 1≤i≤N
• Pentru teste în valoare de 30 de puncte 1 ≤ Z ≤ 1000
• Pentru teste în valoare de 30 de puncte 1 ≤ N ≤ 100
• Pentru teste în valoare de 30 de puncte 2 ≤ P ≤ 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.
• În concurs s-au acordat 10 puncte din oficiu. Pe site se acordă 10 puncte pentru exemple.

Exemplul 1

alinieri.in

4 3 365 
20 11 8 6 

alinieri.out

8

Explicație

N=4, P=3, Z=365 și V1-4 = [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ă 1200,
• planeta 2 efectuează o rotație completă și încă 3000,
• planeta 3 efectuează o rotație completă și încă 1200,
• 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 zile.

Deci în 365 zile vor avea loc 8 alinieri.

Exemplul 2

alinieri.in

7 3 2020 
10 20 10 15 20 10 20  

alinieri.out

3928

Exemplul 3

alinieri.in

6 3 658903 
17 24 12 150 200 12 

alinieri.out

58568