Fişierul intrare/ieşire:divk.in, divk.outSursăpreONI 2006 Runda Finala
AutorFilip Cristian BuruianaAdăugată de
Timp execuţie pe test0.2 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Divk

Fie un vector de N numere naturale nenule. Pentru tripletul (K, A, B) dat trebuie sa raspundem la intrebarea: cate subsecvente ale vectorului dat au lungimea cuprinsa intre A si B ( inclusiv ) si au suma elementelor divizibila cu K?

Cerinta

Sa se determine numarul subsecventelor cu proprietatea enuntata.

Date de Intrare

Prima linie a fisierului divk.in contine patru numere naturale N, K, A si B, separate prin cate un spatiu, avand semnificatia descrisa in enunt. Fiecare din urmatoarele N linii contine cate un numar natural nenul, elementele vectorului.

Date de Iesire

Prima linie a fisierului divk.out contine un numar natural T, numarul de subsecvente cu proprietatea ceruta.

Restrictii si precizari

  • 1 < A < B < N ≤ 500 000
  • 2 ≤ K ≤ 100 000
  • Fiecare numar din cele N nu depaseste 10 000 000 ( 10 milioane )
  • Prin subsecventa intelegem orice insiruire de termeni din vector care sunt pe pozitii consecutive

Exemplu

divk.indivk.out
6 5 2 4
2
9
5
4
1
4
4

Explicatie

Subsecventele care pot fi alese sunt: (2 9 5 4), (4 1), (5 4 1) si (1 4).

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content