Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | contrasens.in, contrasens.out | Sursă | Algoritmiada 2016 - Runda 4 - Juniors |
| Autor | Eugenie Daniel Posdarascu | Adăugată de |  Eugenie Daniel Posdarascu •eudanip |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/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 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
Exemplu
| contrasens.in | contrasens.out |
|---|---|
| 5 2 00 01 10 11 00 | 13 |
