| Fişierul intrare/ieşire: | alinieri.in, alinieri.out | Sursă | OJI 2020, clasa a 10-a |
| Autor | Ciprian Chesca | Adăugată de |  Tamio Vesa Nakajima •tamionv |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 256000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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 (0/zi).
Cerinţă
Cunoscând numărul de planete N şi vitezele lor de rotaţie V[i], 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 V[1..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.
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 ≤ 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
- 2 ≤ P ≤ N ≤ 105
- 1 ≤ Z ≤ 106
- 1 ≤ V[i] ≤ 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.
Exemplu
| alinieri.in | alinieri.out | Explicaţie |
|---|---|---|
| 4 3 365 20 11 8 6 | 8 | N = 4, P = 3, Z = 365 şi V[1..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. |
| 7 3 2020 10 20 10 15 20 10 20 | 3928 | N = 7, P = 3, Z = 2020 şi V[1..7] = [10, 20, 10, 15, 20, 10, 20] În cele 2020 de zile au avut loc 3928 alinieri a minimum 3 planete din cele 7 planete ce formează sistemul solar. |
| 6 3 658903 17 24 12 150 200 12 | 58568 | N = 6, P = 3, Z = 658903 şi V[1..6] = [17, 24, 12, 150, 200, 12] În cele 658903 de zile au avut loc 58568 alinieri a minimum 3 planete din cele 6 planete ce formează sistemul solar. |
