| Fişierul intrare/ieşire: | grea.in, grea.out | Sursă | FMI No Stress 8 |
| Autor | Bogdan Ciobanu, Bogdan Iordache | Adăugată de |  Fmi no stress 2018 •fminostress2018 |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
GrEA
dO YoU gUys nOt HaVe PhOnEs?
Tocmai ti-ai luat cel mai cool joc pe mobil, GrEA: Gravity by EA. Din fericire ai cumparat intreg season pass-ul si ai primit acces si la acest enunt.
In acest joc este vorba de un grid de dimensiune 2xN, format din caracterele 0 si 1.
Gravity Guy, protagonistul jocului, porneste din prima celula de pe prima linie si vrea sa ajunga la ultima coloana, pe oricare dintre linii, cu numar minim de pasi, mergand numai prin celule cu valoarea 0.
Intr-un pas, acesta se poate deplasa pe linia curenta in celule adiacente sau poate schimba gravitatia, trecand pe linia cealalta pe orice coloana care nu are diferenta in valoare absoluta mai mare decat K.
Mai formal, din celula c se poate deplasa in celulele c-1, c+1 de pe randul curent sau celulele t cu |t-c| ≤ K de pe celalalt rand, daca exista si au valoarea 0.
Afisati numarul minim de pasi pentru a ajunge la ultima coloana.
Date de intrare
Fişierul de intrare grea.in contine pe prima linie doua numere intregi, N si K.
Fiecare din urmatoarele 2 linii contine N caractere binare.
Date de ieşire
În fişierul de ieşire grea.out se va afisa raspunsul pe primul rand.
Restricţii
- 1 ≤ K ≤ N ≤ 250.000
- Se garanteaza ca exista o solutie.
Exemplu
| grea.in | grea.out |
|---|---|
| 4 2 0110 0100 | 2 |
