Fişierul intrare/ieşire:subsecvente.in, subsecvente.outSursăInfoarena Monthly 2014, Runda 6
AutorVlad IonescuAdăugată devladiiIonescu Vlad vladii
Timp execuţie pe test0.3 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Subsecvente

Cat timp Antonio este in cautare de lalele, va mai prezentam o problema

Marinica are la dispozitie doua numere naturale cu N cifre, respectiv M cifre. El doreste sa afle cate subsecvente distincte din primul numar (care nu incep cu cifra 0) au proprietatea ca sunt mai mici sau egale decat cel de-al doilea numar. Ajutati-l pe Marinica!

Date de intrare

Fişierul de intrare subsecvente.in va contine doua linii, pe prima linie aflandu-se primul numar, iar pe cea de-a doua, al doilea numar.

Date de ieşire

În fişierul de ieşire subsecvente.out trebuie afisat un singur numar: cate subsecvente distincte din primul numar (care nu incep cu cifra 0) sunt mai mici sau egale decat cel de-al doilea numar.

Restricţii

  • 1 ≤ N ≤ 1.000.000
  • 1 ≤ M ≤ N
  • Atentie! Intr-o subsecventa toate cifrele care apar sunt pe pozitii consecutive in numarul initial. Orice subsecventa poate fi caracterizata de 2 indici i si j, cu i ≤ j, cu proprietatea ca atat elementul de pe pozitia i, cat si cel de pe pozitia j exista, iar subsecventa incepe pe pozitia i si se termina pe pozitia j.
  • Doua subsecvente se considera distincte daca perechile lor de indici difera: (i1, j1) != (i2, j2)

Exemplu

subsecvente.insubsecvente.out
2057
21
4

Explicaţie

Subsecventele numarului 2057 sunt: 2, 0, 5, 7, 20, 05, 57, 205, 057, 2057, dintre care doar urmatoarele sunt mai mici sau egale decat 21 (exceptandu-le pe cele care incep cu cifra 0): 2, 5, 7, 20. Evident celelalte subsecvente nu sunt valide, deoarece 57, 205, 2057 sunt strict mai mari decat 21.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content