Miawinator: Pagină nouă: 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...

2024-01-05T02:24:34Z

Pagină nouă: Se dau <code>n</code> și <code>t</code> două numere naturale nenule și <code>S</code> un șir binar de <code>n</code> elemente indexate de la <code>1</code>. O interschimbare în acest șir constă în alegerea a doi indici <code>i</code>, <code>j</code> (<code>1 ≤ i, j ≤ n</code>) și schimbarea între ele a valorilor <code>S[i]</code> și <code>S[j]</code>. O subsecvență de lungime <code>t</code> a șirului <code>S</code> reprezintă <code>t</code> elemente aflate...

New page

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

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

= Date de intrare =
Pe prima linie a fișierului <code>input.txt</code> se află separate printr-un spațiu numere <code>n</code> și <code>t</code>. Pe a doua linie se află <code>n</code> caractere <code>0</code> și <code>1</code>.

= Date de ieșire =
Pe prima linie a fișierului de ieșire <code>output.txt</code> se va afișa numărul minim de interschimbări necesare pentru obținerea a două subsecvențe disjuncte de lungime <code>t</code> formate doar din elemente egale cu <code>1</code>. Dacă acest lucru este imposibil se va afișa <code>-1</code>.

= Restricții și precizări =

* <code>2 ≤ n ≤ 1.000.000</code>
* <code>2 * t ≤ n</code>

== Exemplul 1 ==
input.txt:

7 2

1010101

output.txt:

2

Explicație:

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

== Exemplul 2 ==
input.txt:

26 3

00010100100100010111001001

output.txt:

1

Explicație:

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

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

3647 - secvente4 - Revision history