Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
北京大学《ACM-ICPC竞赛训练》暑期课面向全球招生。容量有限,报名从速!
Language:
Formula
Time Limit: 3000MSMemory Limit: 65536K
Total Submissions: 79Accepted: 21
Case Time Limit: 2000MSSpecial Judge

Description

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 — E1E2 ∧ ⋯ ∧ En;
  • Disjunction — E1E2 ∨ ⋯ ∨ En.

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

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

Input

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.

Output

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.

Sample Input

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

Sample Output

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

Source

Northeastern Europe 2007, Northern Subregion

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator