| Fişierul intrare/ieşire: | elemente.in, elemente.out | Sursă | Algoritmiada 2011, Runda 3 |
| Autor | Adrian Airinei | Adăugată de |  Airinei Adrian •astronomy |
| Timp execuţie pe test | 0.075 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Elemente
SMB a descoperit o problema cu siruri de numere. Fiind dat un sir S cu N numere naturale, SMB trebuie sa gaseasca numarul de subsiruri distincte care respecta proprietatea ca diferenta dintre oricare doua numere ale subsirului este cel mult egala cu K.
Date de intrare
Fişierul de intrare elemente.in contine pe prima linie doua numere naturale, N si K, separate de un singur spatiu, avand semificatia din enunt. Pe urmatoarele N linii urmeaza elementele sirului initial, cate unul pe o linie.
Date de ieşire
În fişierul de ieşire elemente.out se va afla un singur numar natural Res, care reprezinta restul impartirii numarului de subsiruri distincte cu proprietatea ceruta la 1 000 003.
Restricţii
- 1 ≤ N ≤ 100 000
- 1 ≤ K ≤ 1 000 000 000
- Numerele sirului sunt numere naturale mai mici sau egale cu 2 000 000 000
- Un subsir A = (Si1,Si2,...Sip) este considerat diferit de un subsir B = (Sj1,Sj2,...Sjq) daca p diferit de q sau daca q = p si exista cel putin un indice r astfel incat ir != jr.
- Cel putin 40% din teste vor avea N ≤ 1000
Exemplu
| elemente.in | elemente.out |
|---|---|
| 4 5 8 1 2 3 | 9 |
Explicaţie
Subsirurile sunt: 8, 1, 2, 3, 1 2, 1 3, 2 3, 1 2 3 si 8 3.
Trebuie sa te autentifici pentru a trimite solutii. Click aici
remote content
