# PBinfo #3647 – secvente4 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: deivid

## Enunț

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.

## Cod sursă C++

```cpp
/* Secvente - O(N)
 * Florian Usurelu
 * scor: 100
 */
#include <bits/stdc++.h> 
using namespace std; 
ifstream f ("secvente.in"); 
ofstream g ("secvente.out"); 
const int nmax = 1e6 + 3; 
char s[nmax]; 
int v[nmax], n, st[nmax], dr[nmax], k, sum, sol; 
int main() 
{ 
    f >> n >> k >> (s + 1); 
    for (int i = 1; i <= n; ++i) 
    { 
        v[i] = s[i] - '0'; 
        sum += v[i]; 
    } 
    if (sum < 2 * k) 
    { 
        g << -1; 
        return 0; 
    } 
    sum = 0; 
    for (int i = 1; i <= n; ++i) 
    { 
        sum += v[i]; 
        if(i - k >= 1) 
        { 
            sum -= v[i - k]; 
            st[i] = max(sum, st[i - 1]); 
        } 
        if(i == k) st[i] = sum; 
    } 
    sum = 0; 
    for (int i = n; i >= 0; --i) 
    { 
        sum += v[i]; 
        if(i + k <= n) 
        { 
            sum -= v[i + k]; 
            dr[i] = max(sum, dr[i + 1]); 
        } 
        if(i == n - k + 1) dr[i] = sum; 
    } 
    sol = 2e9; 
    for (int i = k; i + 1 <= n - k + 1; ++i) 
        sol = min(sol, 2 * k - st[i] - dr[i + 1]); 
    g << sol; 
    return 0; 
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3647)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3647/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3647/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)