Разбор добавил Антон Ковшаров

Для быстрого решения необходимо разобрать все 16 случаев данной будевой функции. Очевидно, что невозможно получить единицу только для 0000. Если же функция выдаёт единицу для двух единиц то выгоднее всего напечатать n единиц (отметаем сразу восемь вариантов функции). Иначе если функция возвращает единицу для 01, то если n нечётно выводим все единицы (напр: 111>01>1,т.к. остались варианты когда для двух единиц 0), если чётно, то 0 и n-1 еденицу, после первой операции выражение сведётся к предыдущему. Осталось три варианта 0010, 1000, 1010. Если для двух нолей единица,то выведем n-1 (единицу которая в итоге даст 0) и ещё один ноль. И наконец для 0010 существует только один способ: 1 и n-1 ноль.