Diferente pentru problema/contrasens intre reviziile #3 si #8

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="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.
h2. Date de intrare
Fişierul de intrare $contrasens.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $contrasens.out$ ...
Fişierul de ieşire $contrasens.out$ va contine un singur numar natural reprezentand numarul total de drumuri distincte $modulo 666013$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ P ≤ N ≤ 100.000$
* Pentru $40%$ din teste $N ≤ 500$
h2. Exemplu
|13
|
h2. 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$
 
== include(page="template/taskfooter" task_id="contrasens") ==

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.