secvente

Time limit: 0.04s Memory limit: 64MB Input: secvente.in Output: secvente.out

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

Cerință

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

Date de intrare

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

Restricții și precizări

  • 2n1 000 0002 \leq n \leq 1\ 000\ 000
  • 2tn2 \cdot t ≤ n

Exemplul 1

secvente.in

7 2
1010101

secvente.out

2

Explicație

Elementul de pe poziția 11 se interschimbă cu elementul de pe poziția 66, iar elementul de pe poziția 33 se interschimbă cu elementul de pe poziția 44.

Exemplul 2

secvente.in

26 3
00010100100100010111001001

secvente.out

1

Explicație

O secvență convenabilă se situează între pozițiile 44 și 66 și alta între pozițiile 1818 și 2020. Este nevoie de o singură interschimbare pentru a pune un element de 11 pe poziția 55.

Log in or sign up to be able to send submissions!