Fişierul intrare/ieşire:contrasens.in, contrasens.outSursăAlgoritmiada 2016 - Runda 4 - Juniors
AutorEugenie Daniel PosdarascuAdăugată deeudanipEugenie Daniel Posdarascu eudanip
Timp execuţie pe test0.1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Contrasens

Bossanip si-a cumparat de curand o motocicleta si s-a gandit sa se plimbe cu ea pe strada pe contrasens (nu incercati asta acasa). Desi foarte putine la numar, Bossanip si-a selectat o strada cu 2 benzi. Mai mult, avem si 2 benzi de urgenta (una pe partea stanga si una pe dreapta). Cele 2 benzi de pe sosea au multe gropi pe care le putem considera ca fiind obstacole ce trebuie evitate (benzile de urgenta nu au nici o groapa deoarece nimeni nu le foloseste).

Putem considera soseaua ca o matrice binara de dimensiune N * 2 unde 0 este casuta libera si 1 este groapa. Daca ar fi sa introducem si benzile de urgenta, matricea s-ar transforma intr-o matrice de N * 4 unde prima si ultima coloana sunt mereu 0. Scopul lui Bossanip este sa porneasca din orice pozitie libera de pe prima linie si sa ajunga in orice pozitie libera de pe ultima linie. Singura restrictie pe care acesta o are este ca nu are voie sa mearga mai mult de P casute consecutive pe banda de urgenta (altfel vine politia si Bossanip vrea sa isi pastreze cazierul curat).

Stiind ca la orice moment de timp Bossanip se poate muta doar de la o linie x la linia x + 1 si poate schimba coloana cu maxim 1 pozitie mai la stanga sau mai la dreapta, ajutati-l pe marele sofer sa afle cate drumuri distincte exista care pornesc dintr-o pozitie libera din prima linie si ajung intr-o pozitie libera din ultima linie (considerand inclusiv benzile de urgenta). Doua drumuri sunt considerate distincte daca difera prin cel putin o pozitie la un moment dat.

Date de intrare

Fişierul de intrare contrasens.in va contine pe prima linie 2 numere naturale N si P. Pe urmatoarele linii se afla o matrice binara N * 2 reprezentand soseaua data.

Date de ieşire

Fişierul de ieşire contrasens.out va contine un singur numar natural reprezentand numarul total de drumuri distincte modulo 666013.

Restricţii

  • 1 ≤ P ≤ N ≤ 100.000
  • Pentru 40% din teste N ≤ 500

Exemplu

contrasens.incontrasens.out
5 2
00
01
10
11
00
13

Explicatii

Unul din cele 13 drumuri este urmatorul, marcat cu X.
000X
001X
01X0
011X
000X.

Urmatorul drum nu este valid, deoarece Bossanip petrece 3 momente de timp pe banda de urgenta din dreapta.

00X0
001X
010X
011X
00X0

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?