Роботы и мигающая лента

В школьной лаборатории роботы украшают коридор лентой из n лампочек. Каждая лампочка либо горит (1), либо не горит (0).

Роботы хотят, чтобы на ленте горело ровно k лампочек, но безопасность требует: две соседние лампочки не могут гореть одновременно.

Если вариантов несколько, роботы выбирают тот, который выглядит «самым спокойным»: лексикографически минимальную двоичную строку длины n.

Если сделать ленту невозможно — выведите -1.

Формат ввода

Даны два целых числа n и k.

Формат вывода

Выведите двоичную строку длины n, состоящую из символов 0 и 1, удовлетворяющую условиям, и среди всех таких строк — лексикографически минимальную. Если решения нет, выведите -1.

Ограничения

• 2 ≤ n ≤ 2000
• 0 ≤ k ≤ n
• В строке не должно быть подстроки 11.

Пример

Ввод:

7 3

Вывод:

0010101

Ключевое наблюдение: лексикографически минимальная двоичная строка — та, где как можно дольше идут нули слева. Значит, если у нас фиксировано ровно k единиц и нельзя 11, то «спокойнее всего» поставить единицы как можно правее, оставив левую часть нулевой.

Сначала проверим, возможно ли вообще: максимум единиц без соседства получается, если ставить их через одну: 1010.... Тогда max_ones = (n + 1) // 2. Если k > max_ones, ответа нет.

Почему жадный приём работает: выбирая позиции единиц справа налево с шагом 2, мы не создаём 11 и одновременно минимизируем первый индекс, где строка может отличаться от другой допустимой строки (у нас там будет 0, а у любой альтернативы с единицей левее — 1, значит она хуже).

План:

• Если k > (n + 1) // 2, вывести -1.
• Создать массив/строку из n нулей.
• Идти по индексам i = n-1, n-3, n-5, ... и пока k > 0:
• поставить s[i] = '1', уменьшить k.
• Вывести получившуюся строку.

Мини-сниппет:

• max_ones = (n + 1) // 2
• цикл по позициям: for i in range(n-1, -1, -2): ...

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

Частая ошибка: строить слева направо, ставя единицу «как можно раньше» — это даёт лексикографически максимальный вариант, а нужен минимальный (единицы должны уезжать вправо).