divk

Divk

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

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

Poveste ...

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. Restrictii

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 intrare

h2. Date de Iesire

...

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

h2. Date de iesire

h2. Restrictii si precizari

...

* $1 < A < B < N &le; 500 000$
* $2 &le; K &le; 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

h2. Exemplu

| divk.in | divk.out |
| linia1
linia2
linia3
| linia1
linia2
|

table(example). |_. divk.in |_. divk.out |
|6 5 2 4
2
9
5
4
1
4 | 4 |

== include(page="template/taskfooter" task_id="divk") ==

h3. Explicatie
 
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")==
 
 

926