Fişierul intrare/ieşire:sir5.in, sir5.outSursăInfoarena Monthly 2012, Runda 11
AutorVlad IonescuAdăugată devladiiIonescu Vlad vladii
Timp execuţie pe test1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.insir5.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?