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
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))