Fişierul intrare/ieşire:grea.in, grea.outSursăFMI No Stress 8
AutorBogdan Ciobanu, Bogdan IordacheAdăugată defminostress2018Fmi no stress 2018 fminostress2018
Timp execuţie pe test0.25 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/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.ingrea.out
4 2
0110
0100
2
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?