Login with GitHub. Nope?
修正 C++ 的程式碼在使用一定量動態記憶體後會產生 RF 的問題 @ 2019/12/6 4:45pm NeoHOJ 強勢復活中 (Open beta)
Submit  Ranklist

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
1

Source:

2014 NTUIM PDAO

Problem Setter

Testdata:

TestTimeMemoryScore
01000ms262144kb
11000ms262144kb10
21000ms262144kb10
31000ms262144kb10
41000ms262144kb10
51000ms262144kb10
61000ms262144kb10
71000ms262144kb10
81000ms262144kb10
91000ms262144kb10
101000ms262144kb10