Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | sir5.in, sir5.out | Sursă | Infoarena Monthly 2012, Runda 11 |
| Autor | Vlad Ionescu | Adăugată de |  Ionescu Vlad •vladii |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Sir5
Desi spera la o masinuta cu radiotelecomanda, Marian a primit de la Mos Craciun o problema. Revoltat, vrea sa ii trimita Mosului rezolvarea (alaturi de niste urari frumoase), insa pentru aceasta are nevoie de ajutorul vostru.
Se da un sir binar (format doar din caracterele 1 si 0) de lungime N si trebuie sa plasati intervale inchise ($0$ sau mai multe) de lungime data L peste acest sir, cu urmatoarele proprietati:
- oricare doua intervale nu se intersecteaza;
- intervalele vor fi complet incluse in sir (capetele nu au voie sa depaseasca extremitatile sirului);
- orice interval trebuie sa contina in interiorul sau cel putin un 1;
- nu este obligatoriu ca fiecare element din sir sa fie acoperit de un interval.
Determinati in cate moduri se pot plasa aceste intervale peste sir, modulo 666013.
Sirul va fi dat sub forma unei vector de elemente: A 1 A 2 ... A M, cu semnificatia: primele A 1 elemente din sir au valoarea 1, urmatoarele A 2 elemente au valoarea 0, urmatoarele A 3 sunt 1, urmatoarele A 4 sunt 0 si tot asa.
Date de intrare
Fişierul de intrare sir5.in contine pe prima linie doua numere naturale M si L, despartite prin cate un spatiu, cu semnificatia din enunt. Pe a doua linie se gasesc M numere naturale, despartite prin cate un spatiu, numere care reprezinta elementele vectorului A.
Date de ieşire
În fişierul de ieşire sir5.out se va afla pe prima linie un singur numar natural, care semnifica numarul de moduri in care se pot amplasa intervale inchise de lungime L peste sirul binar, cu proprietatile din enunt, modulo 666013.
Restricţii
- 2 ≤ M ≤ 50
- 2 ≤ L ≤ 50
- 2 ≤ A 1 + A 2 + ... + A M ≤ 1.000.000.000
Exemplu
| sir5.in | sir5.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
