Strada
principala a orasului Bitland este un dreptunghi cu vârfurile în
punctele (0, 0),
(0, 2),
(N, 2),
(N, 0),
acoperit 2xN cu dale cu latura
1m.
Noaptea
în Bitland a viscolit, ca urmare unele dintre dale sunt acoperite cu zapada.
Masina pentru curatarea drumurilor are o lama cu lungimea 1 m. Initial masina
este amplasata astfel încât extremitatile lamei au coordonatele
(K, 0)
si (K, 1).
Intr-o secunda masina se deplaseaza cu exact 1
m, curatind zapada de pe intreaga dala parcursa. Daca este necesar, masina se
poate deplasa si lateral (mai exact lama poate ajunge din pozitia (K,0)-(K,1)
in pozitia (K,1)-(K,2) sau invers).
Deplasarea in laterala se realizeaza instantaneu.
Cerinta
Scrieti un program care sa determine numarul minim de secunde necesare pentru
curatarea zapezii de pe strada principala.
Date
de intrare
Fisierul de intrare zapada.in
contine pe prima linie doua numere naturale N
K separate prin spatiu, cu semnificatia
din enunt. Urmatoarele N linii
contin câte 2 numere din
multimea {0, 1}
separate prin cate un spatiu (primul numar de pe linia i+1
este 1 daca patratelul cu coltul
stanga-jos (i,0)
este acoperit cu zapada si 0
in caz contrar; al doilea numar este 1
daca patratelul cu coltul stanga-jos (i,1)
este acoperit cu zapada si 0
in caz contrar).
Date
de iesire
Fisierul de iesire zapada.out
va contine o singura linie pe care va fi scris un singur numar natural reprezentand
numarul minim de secunde necesare pentru deszapezirea strazii principale.
Restrictii
si precizari
1 <= N <= 1000
0 <= K <= N
În timpul lucrului masina nu poate parasi strada.
Pozitia finala a masinii poate fi oricare.
Exemplu
zapada.in
zapada.out
zapada.in
zapada.out
4 0
0 0
1 1
0 0
0 1
6
4
0
0 0
0 1
0 0
1 1
5
prof. Sergiu Corlat
Liceul Moldo-Turc
Chisinau
Contact:scorlat@gmail.com