| Fişierul intrare/ieşire: | subsecvente.in, subsecvente.out | Sursă | Infoarena Monthly 2014, Runda 6 |
| Autor | Vlad Ionescu | Adăugată de |  Ionescu Vlad •vladii |
| Timp execuţie pe test | 0.15 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | subsecvente.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.
