| 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) 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.
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 ≤ 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.
Exemplu
| sir5.in | sir5.out |
|---|---|
| 4 3 3 2 2 3 | 19 |
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.
