Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | divk.in, divk.out | Sursă | preONI 2006 Runda Finala |
| Autor | Filip Cristian Buruiana | Adăugată de | |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate |   1/5 |
Vezi solutiile trimise | Statistici
Divk
| Aceasta pagina a fost importata din infoarena1 si nu este inca prelucrata. Sterge ==Include(file="template/raw")== cand esti multumit cu continutul paginii. |
|---|
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
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
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).
