#P18272. Boolean Function Reconstruction
Boolean Function Reconstruction
Boolean Function Reconstruction
给定一个以 个布尔变量为输入的布尔函数的完整真值表,请构造一个实现该函数的布尔表达式。只能使用逻辑与 & 和逻辑或 |,不能使用取反。
合法表达式 <expr> 必须严格符合以下递归语法:
T、F:分别表示真、假。a、b、……:第 个变量用第 个小写英文字母表示,只能使用本测试用例给出的 个变量。(<expr>&<expr>):两个表达式的逻辑与。(<expr>|<expr>):两个表达式的逻辑或。
两种运算的真值表如下。
| 0 | 0 | 0 | 0 |
| 1 | 1 | ||
| 1 | 0 | ||
| 1 | |||
判断是否存在符合要求的表达式。若存在,你输出的表达式中,二元运算符(& 和 |)的总数不得超过 ,括号嵌套深度不得超过 。可以证明,只要该函数能够用上述运算表示,就一定有满足这两个限制的表达式。
输入格式
第一行一个整数 ,表示测试用例数,。
每个测试用例占两行:
- 第一行一个整数 ,。
- 第二行一个长度恰为 的二进制字符串 ,表示函数真值表。
具体地,当第 个变量的取值为 时,函数值等于字符串 的第
个字符(字符串下标从 开始)。因此,变量 a 对应二进制下标的最低位。
保证同一输入文件内所有测试用例满足
输出格式
每个测试用例先输出一行 Yes 或 No,表示是否存在满足要求的表达式。
若输出 Yes,下一行输出一个合法表达式。表达式必须严格遵守上述格式,不得添加或省略括号,也不得含有额外空格。可以输出任意一个满足真值表、运算符数量和嵌套深度限制的表达式。
样例输入
7
2
0001
2
0111
2
1111
3
00010111
1
10
2
0101
5
00000000000000000000000000000001
样例输出
Yes
(a&b)
Yes
(a|b)
Yes
T
Yes
((a&(b|c))|(b&c))
No
Yes
a
Yes
(a&(b&(c&(d&e))))
样例说明
第四个测试用例的真值表如下(列顺序与原题一致, 对应 a)。
| 0 | 0 | 0 | 0 |
| 1 | |||
| 1 | 0 | ||
| 1 | |||
| 1 | 0 | 0 | |
| 1 | 1 | ||
| 1 | 0 | ||
| 1 | |||
表达式 ((a&(b|c))|(b&c)) 满足该真值表。其他等价且满足限制的表达式也合法。