Реши задание на изображении

Ответ — программа на Python 3. Она восстанавливает лексикографически минимальную строку за \(O(n)\).

import sys

def solve():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    n, k = data[0], data[1]
    m = n - k + 1
    s = data[2:2 + m]

    # delta[i] = s[i+1] - s[i]
    delta = [s[i + 1] - s[i] for i in range(m - 1)]

    # can0[r], can1[r] — можно ли поставить первым битом
    # цепочки позиций r, r+k, r+2k, ... соответственно 0 или 1
    can0 = [False] * k
    can1 = [False] * k

    for r in range(k):
        v0, v1 = 0, 1
        ok0 = ok1 = True
        pos = r

        while pos + k < n:
            d = delta[pos]
            v0 += d
            v1 += d

            if not (0 <= v0 <= 1):
                ok0 = False
            if not (0 <= v1 <= 1):
                ok1 = False

            pos += k

        can0[r] = ok0
        can1[r] = ok1

    # Минимальное и максимальное число единиц,
    # которое можно набрать в суффиксе первых k бит
    suf_min = [0] * (k + 1)
    suf_max = [0] * (k + 1)

    for i in range(k - 1, -1, -1):
        suf_min[i] = suf_min[i + 1] + (0 if can0[i] else 1)
        suf_max[i] = suf_max[i + 1] + (1 if can1[i] else 0)

    need = s[0]
    x = [0] * n

    # Жадно строим лексикографически минимальные первые k бит
    for i in range(k):
        if can0[i] and suf_min[i + 1] <= need <= suf_max[i + 1]:
            x[i] = 0
        else:
            x[i] = 1
            need -= 1

    # Восстанавливаем остальные биты
    for i in range(n - k):
        x[i + k] = x[i] + delta[i]

    sys.stdout.write(''.join(map(str, x)) + '\n')


if __name__ == "__main__":
    solve()

Почему это работает

Для двух соседних окон:

\[ s_i-s_{i+1}=x_i-x_{i+k} \]

Значит:

\[ x_{i+k}=x_i+s_{i+1}-s_i \]

То есть позиции с одинаковым остатком по модулю \(k\) образуют цепочку:

\[ r,\ r+k,\ r+2k,\dots \]

Если выбрать первый бит цепочки, все остальные в ней восстанавливаются однозначно. Поэтому для каждого \(r\) проверяем, возможен ли первый бит \(0\), и возможен ли \(1\).

Первые \(k\) бит должны давать сумму \(s_1\). Грееде выбираем \(0\), если оставшиеся позиции всё ещё можно дополнить до нужного количества единиц; иначе ставим \(1\). Так как именно первые \(k\) бит сравниваются в первую очередь, получается лексикографически минимальный ответ.

Проверка на образцах

Для входа:

5
3
1
2
1

получается 01010: суммы окон 010 = 1, 101 = 2, 010 = 1.

Для входа:

4
2
1
1
1

получается 0101: суммы окон 01 = 1, 10 = 1, 01 = 1.

Сложность: \(O(n)\) по времени и \(O(n)\) по памяти.