Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

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

(Время: 1 сек. Память: 16 Мб Сложность: 45%)

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

Если задана булева функция f и набор из N булевых значений a1, a2, ..., aN , то результат цепного вычисления этой булевой функции определяется следующим образом:

  • если N = 1, то он равен a1;
  • если N > 1, то он равен результату цепного вычисления булевой функции f для набора из (N–1) булевого значения f(a1,a2), a3, …, aN, который получается путем замены первых двух булевых значений в наборе из N булевых значений на единственное булево значение – результат вычисления функции f от a1 и a2.

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

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

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

Входные данные

Первая строка входного файла INPUT.TXT содержит одно натуральное число N (2 ≤ N ≤ 100 000). Вторая строка содержит описание булевой функции в виде четырех чисел, каждое из которых – ноль или единица.

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

Выходные данные

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

Примеры

INPUT.TXTOUTPUT.TXT
14
0110
1011
25
0100
11111
36
0000
No solution

Пояснение

В первом примере процесс вычисления цепного значения булевой функции f происходит следующим образом: 1011 → 111 → 01 → 1.

Во втором примере вычисление цепного значения булевой функции f происходит следующим образом: 11111 → 0111 → 111 → 01 → 1.

В третьем примере получить цепное значение булевой функции f, равное 1, невозможно.


Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]

Красноярский краевой Дворец пионеров, (c)2006 - 2018, ICQ: 151483, E-mail: admin@acmp.ru