Fişierul intrare/ieşire:alinieri.in, alinieri.outSursăOJI 2020, clasa a 10-a
AutorCiprian ChescaAdăugată detamionvTamio Vesa Nakajima tamionv
Timp execuţie pe test0.2 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/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.inalinieri.outExplicaţ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.
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?