Problem : 346 - Evaluation Order

Problem Statistics

Solved Member: 4　　Submission: 46　　User Tried: 5

Statement:

　　邏輯運算領域中有一種技術叫快捷運算（short-circuit evaluation），意思是在一個邏輯運算式中，我們可能會因為某些邏輯上的推論使得我們不需要檢查所有的布林變數就可以確定整個運算式的真偽。對於一個運算式，我們可以把某些運算順序交換，使得該運算式語意不變，並且讓我們檢查的布林變數數量盡量的小。
例如： (A, B, C) = (false, true, false)
(B && C) || !A 需要檢查3個變數
!A || (B && C) 則只需檢查1個變數A，因為!A是true則整式為true
　　今天西瓜瓜確定了一個邏輯運算式中每個變數的真偽值，他想要請教你，
在任意改變順序之後檢查變數數量最小可能是多少？

請注意，!運算子運算優先於&&，而&&優先於||。

Input:Output:

　　輸入包含多筆測試資料。輸入的第一行是一個整數N，代表總共有N個布林變數，這N個變數用 #編號來表示（例如：#0），而編號為0~N-1。第二行有N個數字，這N個數字只會是0或1，其中第i個數字代表#i-1為1(T)/0(F)。輸入的第三行為一個長度不超過10000的字串，為這筆測試資料要考慮的表達式，該表達式中所有標點符號（只會有!、&&、||和左右括號）、變數都會用空格隔開。當輸入N為0時結束。

　　對每一筆測試資料請輸出一行，包含一個數字，代表該筆測試資料之表達式經過變換後最少只要考慮幾個變數。當N為0時請不要輸出任何東西。

Sample Input:Sample Output:

3
0 1 0
( #1 && #2 ) || ! #0
0

Source:

2014 NTUIM PDAO

Problem Setter

bigelephant29

Testdata:

Test	Time	Memory	Score
0	1000ms	262144kb
1	1000ms	262144kb	10
2	1000ms	262144kb	10
3	1000ms	262144kb	10
4	1000ms	262144kb	10
5	1000ms	262144kb	10
6	1000ms	262144kb	10
7	1000ms	262144kb	10
8	1000ms	262144kb	10
9	1000ms	262144kb	10
10	1000ms	262144kb	10