07/04/2025 00:25:07

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

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

Задачи

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

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

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

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

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

Задачи

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)