3647 - secvente4

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 input.txt 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 output.txt 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

input.txt:

7 2

1010101

output.txt:

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

input.txt:

26 3

00010100100100010111001001

output.txt:

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.

Exemplul 3

input.txt:

9999999999999999 3

00010100100100010111001001

Output:

Input-ul nu convine conditiilor

Rezolvare

<syntaxhighlight lang="python3" line="1"> def verificare(n,t):

   if not(2<=n<=1000000):
       print("Input-ul nu convine conditiilor")
       exit()
   if not(2*t<=n):
       print("Input-ul nu convine conditiilor")
       exit()

with open("input.txt", "r") as f, open("output.txt", "w") as g:

   n, k = map(str, f.readline().split())
   s = f.readline()
   n = int(n)
   k = int(k)
   verificare(n,k)

   v = [int(ch) for ch in s]
   st = [0] * (n + 1)
   dr = [0] * (n + 1)
   
   sum_value = sum(v)

   if sum_value < 2 * k:
       g.write("-1")
       exit()

   sum_value = 0

   for i in range(1, n + 1):
       sum_value += v[i - 1]
       if i - k >= 1:
           sum_value -= v[i - k - 1]
           st[i] = max(sum_value, st[i - 1])

       if i == k:
           st[i] = sum_value

   sum_value = 0

   for i in range(n, 0, -1):
       sum_value += v[i - 1]
       if i + k <= n:
           sum_value -= v[i + k - 1]
           dr[i] = max(sum_value, dr[i + 1])

       if i == n - k + 1:
           dr[i] = sum_value

   sol = 2e9

   for i in range(k, n - k + 1):
       sol = min(sol, 2 * k - st[i] - dr[i + 1])

   g.write(str(sol))

</syntaxhighlight>