Fişierul intrare/ieşire:elemente.in, elemente.outSursăAlgoritmiada 2011, Runda 3
AutorAdrian AirineiAdăugată deastronomyAirinei Adrian astronomy
Timp execuţie pe test0.15 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.inelemente.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

Cum se trimit solutii?

remote content