← 返回题目列表

Codeforces · 913/E

E. 逻辑表达式

中文机器翻译题面 查看原题

给定一个由三个变量组成的布尔函数,该函数由其真值表定义。您需要找到一个等于该函数的最小长度的表达式。该表达式可能包括:

- AND 运算('&',ASCII 代码 38)
- 运算 OR('|',ASCII 代码 124)
- NOT 运算('!',ASCII 代码 33)
- 变量 x、y 和 z(ASCII 代码 120-122)
- 括号('(',ASCII 代码 40,和 ')',ASCII 代码 41)

如果存在多个最小长度的表达式,您应该找到按字典顺序最小的一个。

操作具有标准优先级。 NOT 具有最高优先级,然后是 AND,OR 具有最低优先级。表达式应满足以下语法:

E ::= E '|' T |时间

T ::= T '&' F | F

F ::= '!' F | '('E')'| 'x' | 'y'| 'z'

输入

第一行包含一个整数 n — 输入中函数的数量 (1 ≤ n ≤ 10 000)。

接下来的n行是函数的描述,其中第i行包含一个长度为8的字符串,由数字0和1组成——第i个函数的真值表。位置 j (0 ≤ j < 8) 上的数字等于 $$x = \left\lfloor \frac{2}{4} \right\rfloor$$、$$y = \left\lfloor \frac{i}{2} \right\rfloor \bmod 2$$ 和 $$z = j \bmod 2$$ 情况下的函数值。

输出

你应该输出n行,第i行应该包含等于第i个函数的最小长度的表达式。如果有多个这样的表达式,则输出其中按字典顺序最小的一个。表达式应该满足给定的语法并且不应包含空格。

示例

输入 #1

4
00110011
00000111
11110000
00011111

输出 #1

y
(y|z)&x
!x
x|y&z

注意

第二个函数的真值表: