== include(page="template/taskheader" task_id="sir5") ==
Poveste şi cerinţă...
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$) 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$;
Determinati in cate moduri se pot plasa aceste intervale peste sir, modulo $666013$.
Sirul va fi dat sub forma unui vector de $M$ 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.
h2. Date de intrare
Fişierul de intrare $sir5.in$ ...
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$.
h2. Date de ieşire
În fişierul de ieşire $sir5.out$ ...
Î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$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $2 ≤ M ≤ 30$
* $2 ≤ L ≤ 30$
* $1 ≤ A ~i~ ≤ 1.000.000.000$
* $L ≤ A ~1~ + A ~2~ + ... + A ~M~ ≤ 1.000.000.000$
* Doua asezari se considera distincte daca numarul de intervale difera sau daca exista o pozitie in care intr-un amplasament incepe un interval, iar in celalalt nu.
* Nu este obligatoriu ca fiecare element din sir sa fie acoperit de un interval.
* Nu uitati ca si cazul in care nu se plaseaza niciun interval este valid.
h2. Exemplu
table(example). |_. sir5.in |_. sir5.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4 3
3 2 2 3
| 19
|
h3. Explicaţie
...
Sirul binar corespunzator exemplului este: $1110011000$.
Exemple de intervale adaugate corect:
@111[001][100]0@, @11[100]11000@, @1[110]0[110]00@.
Exemple de intervale adaugate incorect:
@1110011[000]@ -> caci in interiorul intervalului nu se afla niciun $1$.
@111[00[1]10]00@ -> caci intervalele se intersecteaza.
== include(page="template/taskfooter" task_id="sir5") ==
