Rezolvare PBinfo #3647

Se dau n și t două numere naturale nenule și S un șir binar de n elemente indexate de la 1. O interschimbare în acest șir constă în alegerea a doi indici i, j (1 ≤ i, j ≤ n) și schimbarea între ele a valorilor S[i] și S[j]. O subsecvență de lungime t a șirului S reprezintă t elemente aflate pe poziții consecutive în șirul S.

Cerința

Să se determine numărul minim de interschimbări ce trebuie realizate în șirul S pentru a obține două subsecvențe disjuncte de lungime t formate doar din elemente egale cu 1.

Date de intrare

Pe prima linie a fișierului secvente.in se află separate printr-un spațiu numere n și t. Pe a doua linie se află n 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 t formate doar din elemente egale cu 1. Dacă acest lucru este imposibil se va afișa -1.

Restricții și precizări

• 2 ≤ n ≤ 1.000.000
• 2 * t ≤ n

Exemplul 1:

secvente.in

7 2
1010101

secvente.out

2

Explicație

Elementul de pe poziția 1 se interschimbă cu elementul de pe poziția 6, iar elementul de pe poziția 3 se interschimbă cu elementul de pe poziția 4.

Exemplul 2:

secvente.in

26 3
00010100100100010111001001

secvente.out

1

Explicație

O secvență convenabilă se situează între pozițiile 4 și 6 și alta între pozițiile 18 și 20. Este nevoie de o singură interschimbare pentru a pune un element de 1 pe poziția 5.