[UVA] 11357 - Ensuring Truth＠Morris' Blog｜PChome Online 個人新聞台

2013-06-13 20:45:06| 人氣1,053| 回應0 | 上一篇 | 下一篇

[UVA] 11357 - Ensuring Truth

推薦 0 收藏 0 轉貼0 訂閱站台

E	NEXT generation Contest - 4	Time Limit – 3 secs
	Ensuring Truth

In this problem we will consider Boolean formulas written according to the following BNF grammar:

<formula> ::= <clause> | <formula> "|" <clause>

<clause> ::= "(" <conjunction-of-literals> ")"

<conjunction-of-literals> ::= <literal> | <conjunction-of-literals> "&" <literal>

<literal> ::= <variable> | "~" <variable>

<variable> ::= "a" | "b" | "c" | ... | "z"

Each formula can contain up to 26 different Boolean variables, which are denoted by lowercase English letters. We use the ampersand sign ("&") to denote conjunction, vertical bar ("|") for disjunction, and tilde ("~") for inversion. The truth tables of these operators are shown below for your reference.

x	y	x & y
false	false	false
false	true	false
true	false	false
true	true	true

x	y	x \| y
false	false	false
false	true	true
true	false	true
true	true	true

x	~x
false	true
true	false

A formula is called satisfiable if it is possible to assign values to its variables in such a way as to make the formula evaluate to true.

Input

The first line of the input file contains an integer T (1 ≤ T ≤ 5000). Each of the next T lines contains a Boolean formula. You can assume that the formulas will strictly follow the grammar specified above, and will not be longer than 250 characters.

Output

For each formula, you should determine whether it is satisfiable, and output a line "YES" if yes, it is, and "NO" otherwise.

Sample Input

Output for Sample Input

(a&b&c)|(a&b)|(a)

(x&~x)

YES

NO

ProblemSetter: Ivan Krasilnikov

乍看之下以為是 NPC 問題。其實不是的。

由於 BNF 語法出來只會有 (&&&&) | (&&&&&) | ...
並不會存在 not exist (&&&&(&&&|&&&))。

因此只要考慮其中一個存在 (&&&&&) = true 就大功告成了。

#include <stdio.h>
char s[1005];
int main() {
    int testcase;
    scanf("%d", &testcase);
   while(testcase--) {
       scanf("%s", s);
       int i, j, yes = 0;
        for(i = 0; s[i]; i++) {
           if(s[i] == '(') {
               int cnt[26] = {};
               while(s[i] != ')') {
                   if(s[i] >= 'a' && s[i] <= 'z') {
                       if(i >= 0 && s[i-1] == '~')
                           cnt[s[i]-'a'] |= 2;
                        else
                           cnt[s[i]-'a'] |= 1;
                      }
                      i++;
                  }
               for(j = 0; j < 26; j++)
                   if(cnt[j] == 3)
                       break;
               if(j == 26)
                   yes = 1;
           }
       }
       puts(yes ? "YES" : "NO");
   }
    return 0;
}

我要檢舉

#11357#Ensuring Truth

台長： Morris

您可能對以下文章有興趣

[ACM-ICPC][Greedy解] 5864 - Register Allocation

[UVA] 10536 - Game of Euler

[UVA][正環][spfa] 10557 - XYZZY

[UVA][遞迴] 12208 - How Many Ones Needed?

人氣(1,053) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA] 604 - The Boggle Game
此分類上一篇:[UVA][語法判斷] 743 - The MTM Machine

回應(0)