Divk

divk

==Include(page="template/taskheader" task_id="divk")==

== include(page="template/taskheader" task_id="divk") ==
 
Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...
 
h2. Exemplu
 
| divk.in | divk.out |
| linia1
linia2
linia3
| linia1
linia2
|
 
== include(page="template/taskfooter" task_id="divk") ==

==Include(page="template/raw")==
 
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?
 
h2. Cerinta
 
Sa se determine numarul subsecventelor cu proprietatea enuntata.
 
h2. 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.
 
h2. Date de Iesire
 
Prima linie a fisierului divk.out contine un numar natural T, numarul de subsecvente cu proprietatea ceruta.
 
h2. Restrictii si precizari
 
o 1 < A < B < N <= 500 000
o 2 <= K <= 100 000
o Fiecare numar din cele N nu depaseste 10 000 000 ( 10 milioane )
o Prin subsecventa intelegem orice insiruire de termeni din vector care sunt pe pozitii consecutive
 
h2. Exemplu
 
 
 
 
|divk.in |divk.out |
 
|6 5 2 4 |4 |
| | |
|2 | |
| | |
|9 | |
| | |
|5 | |
| | |
|4 | |
| | |
|1 | |
| | |
|4 | |
 
 
 
 
Subsecventele care pot fi alese sunt: (2 9 5 4), (4 1), (5 4 1) si (1 4).
 
 
==Include(page="template/taskfooter" task_id="divk")==