26/04/2024 09:19:48

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

1367. Булева функция

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Недавно на уроке информатики ученики одного из классов изучили булевы функции. Напомним, что булева функция `f` сопоставляет значениям двух булевых аргументов, каждый из которых может быть равен 0 или 1, третье булево значение, называемое результатом. Для учеников, которые выразили желание более подробно изучать эту тему, учительница информатики на дополнительном уроке ввела в рассмотрение понятие цепного вычисления булевой функции `f`.

Если задана булева функция `f` и набор из `N` булевых значений `a_1,\ a_2,\ …,\ a_N`, то результат цепного вычисления этой булевой функции определяется следующим образом:

если `N\ =\ 1`, то он равен `a_1`;
если `N\ >\ 1`, то он равен результату цепного вычисления булевой функции `f` для набора из `(N-1)` булевого значения `f(a_1,a_2),\ a_3,\ …,\ a_N`, который получается путем замены первых двух булевых значений в наборе из `N` булевых значений на единственное булево значение — результат вычисления функции `f` от `a_1` и `a_2`.

Например, если изначально задано три булевых значения: `a_1\ =\ 0`, `a_2\ =\ 1`, `a_3\ =\ 0`, а функция `f` — ИЛИ (OR), то после первого шага получается два булевых значения — (0 OR 1) и 0, то есть, 1 и 0. После второго (и последнего) шага получается результат цепного вычисления, равный 1, так как 1 OR 0 = 1.

В конце дополнительного урока учительница информатики написала на доске булеву функцию `f` и попросила одного из учеников выбрать такие `N` булевых значений `a_i`, чтобы результат цепного вычисления этой функции был равен единице. Более того, она попросила найти такой набор булевых значений, в котором число единиц было бы как можно большим.

Требуется написать программу, которая решала бы поставленную учительницей задачу.

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

Первая строка входного файла содержит одно натуральное число `N` (`2\ ≤\ N\ ≤\ 100\ 000`).

Вторая строка входного файла содержит описание булевой функции в виде четырех чисел, каждое из которых — ноль или единица. Первое из них есть результат вычисления функции в случае, если оба аргумента — нули, второе — результат в случае, если первый аргумент — ноль, второй — единица, третье — результат в случае, если первый аргумент — единица, второй — ноль, а четвертый — в случае, если оба аргумента — единицы.

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

В выходной файл необходимо вывести строку из `N` символов, определяющих искомый набор булевых значений `a_i` с максимально возможным числом единиц. Если ответов несколько, требуется вывести любой из них. Если такого набора не существует, выведите в выходной файл фразу "No solution".

Пример ввода 1

4
0110

Пример вывода 1

Пример ввода 2

5
0100

Пример вывода 2

Пример ввода 3

6
0000

Пример вывода 3

No solution

Пояснения к примерам
В первом примере процесс вычисления цепного значения булевой функции `f` происходит следующим образом:
`1011\ →\ 111\ →\ 01\ →\ 1`
Во втором примере вычисление цепного значения булевой функции `f` происходит следующим образом:
`11111\ →\ 0111\ →\ 111\ →\ 01\ →\ 1`
В третьем примере получить цепное значение булевой функции `f`, равное 1, невозможно.
Система оценивания
Решения, правильно работающие только при `N\ ≤\ 20`, будут оцениваться из 40 баллов.
Источник: региональный этап Всероссийской олимпиады по информатике 2009/2010, http://neerc.ifmo.ru/school/

22/01/2010	Областная олимпиада школьников по информатике. I тур. (3)
27/02/2010	Занятие 8 (B)