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

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

HotLog


 

Медиана

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

Булевы функции – один из центральных объектов изучения дискретной математики. Множество S булевых функций называют полным, если любая булева функция может быть представлена в виде композиции функций из множества S.

К классическим полным системам функций относят, например, {∨, ∧, ¬} для дизъюнктивной или конъюнктивной нормальной формы, или {⊕, ∧, 1} для полиномов Жегалкина, а также существуют полные системы, состоящие из одной функции стрелка Пирса ↓ (not or), и штрих Шеффера ' (not and).

Большинство полных систем, которые обычно рассматриваются, содержат унарные и бинарные функции. Но есть несколько тернарных операций, которые также представляют особый интерес. Одна из них – медиана: < xyz >, равная 0, если хотя бы два ее аргумента равны 0, и 1 если хотя бы два ее аргумента равны 1. Медиану легко выразить через конъюнкцию и дизъюнкцию:

< xyz > = (x ∧ y) ∨ (y ∧ z) ∨ (z ∧ x) = (x ∨ y) ∧ (y ∨ z) ∧ (z ∨ x).

Функция f(x1, x2, ... , xn) называется самодвойственной, если для любого набора переменных выполнено следующее свойство: f(x1, x2, ... , xn) = f(x1, x2, ..., xn), где x означает not x. Пример самодвойственной функции: f(x, y, z) = x ⊕ y ⊕ z.

Функция f(x1, x2, . . . , xn) называется монотонной, если для любых двух наборов переменных x1, x2, ..., xn и y1, y2, ..., yn, таких что xi ≤ yi для всех i, выполнено следующее свойство: f(x1, x2, ..., xn) ≤ f(y1, y2, ..., yn). Пример монотонной функции: f(x, y, z) = x ∧ y ∧ z.

Легко проверить, что медиана является одновременно самодвойственной и монотонной. Более того, медиана оказывается полной для класса самодвойственных монотонных функция. Это означает, что любая самодвойственная монотонная функция может быть представлена в виде композиции медиан. Например, функция f (u, v, x, y, z) = ((u∨v∨x∨y)∧z)∨(u∧v∧x∧y) может быть представлена в виде f (u, v, x, y, z) = < uz < vz < xzy > > >.

По заданной монотонной самодвойственной функции найдите ее представление с использованием медианы.

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

Входной файл INPUT.TXT содержит формулу самодвойственной монотонной булевой функции. В формуле используются маленькие буквы английского алфавита в качестве переменных, а также следующие операции (в порядке приоритета при вычислении): «!» для not, «&» для and, «|» для or. Скобки как обычно используются для изменения приоритета операций. В формуле используется не более 5 переменных. Длина формулы не превышает 250 символов.

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

В выходной файл OUTPUT.TXT выведите представление функции из входного файла с использованием медианы. Не выводите пробелов. Ваша формула должна содержать не более 50 000 символов.

Примеры

INPUT.TXTOUTPUT.TXT
1x&y|y&z|x&z<xyz>
2xx
3((u|v|x|y)&z)|(u&v&x&y) <uz<vz<xzy>>>

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

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

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