3540：Formula

Special Judge 特殊评判

题目描述

Nick is a mathematician and his speciality is Boolean logic, especially repetition-free functions. The Boolean function is repetition-free if it can be represented as a repetition-free formula. Formula is repetition-free if each variable occurs in the formula only once.

Let us fix the syntax of considered logical formulae:

Variables — letters from ‘a’ to ‘k’;
Parentheses — if E is a formula, then (E) is another;
Negation — ¬E is a formula for any formula E;
Conjunction — E₁ ∧ E₂ ∧ ⋯ ∧ E_n;
Disjunction — E₁ ∨ E₂ ∨ ⋯ ∨ E_n.

The operations are listed from the highest priority to the lowest.

The problem is to represent given Boolean function by a repetition-free formula.

输入解释

The only line of input contains the Boolean function represented as a string consisting of characters ‘a’..‘k’, ‘(’, ‘)’, ‘~’, ‘&’ and ‘|’. The last three tokens stand for ¬, ∧ and ∨ respectively. Tokens can be separated by an arbitrary number of spaces. The line contains 1 000 characters at most. The formula in the file is syntactically correct.

输出解释

The first line of the output file must contain “Yes” if function is repetition-free and “No” otherwise.

In the former case the following line must contain the repetition-free formula for given Boolean function in the same format as in the input file. The line must contain no more than 1 000 characters.

输入样例

#1 (a | b) & (a | c)
#2 d&~d
#3 d & ~d | ~((a|~b) & (a|c))
#4 a & b | ~ a & ~b

#1	(a \| b) & (a \| c)
#2	d&~d
#3	d & ~d \| ~((a\|~b) & (a\|c))
#4	a & b \| ~ a & ~b

输出样例

#1 Yes
a | b & c
#2 No
#3 Yes
~a&(b|~c)
#4 No

#1	Yes a \| b & c
#2	No
#3	Yes ~a&(b\|~c)
#4	No

来自北京大学POJ的附加信息

Case time limit(单组数据时间限制)

2000MS

该题目是Virtual Judge题目，来自北京大学POJ

题目来源 Northeastern Europe 2007, Northern Subregion

源链接： POJ-3540

最后修改于 2020-10-29T07:04:02+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
3000	65536