Se dau și două numere naturale nenule și un șir binar de elemente indexate de la . O interschimbare în acest șir constă în alegerea a doi indici și schimbarea între ele a valorilor și . O subsecvență de lungime a șirului reprezintă elemente aflate pe poziții consecutive în șirul .
Cerință
Să se determine numărul minim de interschimbări ce trebuie realizate în șirul pentru a obține două subsecvențe disjuncte de lungime formate doar din elemente egale cu .
Date de intrare
Pe prima linie a fișierului secvente.in
se află separate printr-un spațiu numere și . Pe a doua linie se află caractere 0
și 1
.
Date de ieșire
Pe prima linie a fișierului de ieșire secvente.out
se va afișa numărul minim de interschimbări necesare pentru obținerea a două subsecvențe disjuncte de lungime formate doar din elemente egale cu . Dacă acest lucru este imposibil se va afișa -1
.
Restricții și precizări
Exemplul 1
secvente.in
7 2
1010101
secvente.out
2
Explicație
Elementul de pe poziția se interschimbă cu elementul de pe poziția , iar elementul de pe poziția se interschimbă cu elementul de pe poziția .
Exemplul 2
secvente.in
26 3
00010100100100010111001001
secvente.out
1
Explicație
O secvență convenabilă se situează între pozițiile și și alta între pozițiile și . Este nevoie de o singură interschimbare pentru a pune un element de pe poziția .