TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

66.7% (2/3)

Submission's AC Ratio

85.7% (6/7)

Description

給你一個由邏輯閘構成的樹狀數位電路,你有辦法讓這個數位電路輸出0(false)嗎?

Input Format

第一行有一個正整數$N$,代表數位電路有幾個輸入。第二行有$K$個以空白隔開的字串,代表給定的樹狀數位電路的前序表達式,其中$N$個輸入分別以x0x1、……、x(N-1)表示(不含括號,例如若$N=100$,則最後一個輸入以x99表示)。not邏輯閘只有一個輸入,其餘邏輯閘皆有兩個輸入。

對於所有測資,$N\leq 120,K\leq 5000$。
對於62%的測資,$N\leq 16,K\leq 1000$。

Output Format

輸出$N$行,每行包含一個字串,代表使該數位電路輸出0的一組解,其中第$i$行代表第$i$個輸入。保證一定有解。

Sample Input

#Sample Input 1
3
or and x0 x1 or and x1 not x2 and x0 x2
#Sample Input 2
5
or and x0 not x1 and x2 not x3

Sample Output

#Sample Output 1
0
1
1
#Sample Output 2
0
1
0
1
0

Hints

第一筆範例測資的圖示如下:

Problem Source

TIOJ第一屆愚人節比賽:pC

Subtasks

No. Testdata Range Score
1 0~5 31
2 6~11 31
3 12~16 17
4 17~21 17
5 0~27 2
6 0~35 2

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1500 262144 262144 1 5 6
1 1500 262144 262144 1 5 6
2 1500 262144 262144 1 5 6
3 1500 262144 262144 1 5 6
4 1500 262144 262144 1 5 6
5 1500 262144 262144 1 5 6
6 1500 262144 262144 2 5 6
7 1500 262144 262144 2 5 6
8 1500 262144 262144 2 5 6
9 1500 262144 262144 2 5 6
10 1500 262144 262144 2 5 6
11 1500 262144 262144 2 5 6
12 2500 262144 262144 3 5 6
13 2500 262144 262144 3 5 6
14 2500 262144 262144 3 5 6
15 2500 262144 262144 3 5 6
16 2500 262144 262144 3 5 6
17 2500 262144 262144 4 5 6
18 2500 262144 262144 4 5 6
19 2500 262144 262144 4 5 6
20 2500 262144 262144 4 5 6
21 2500 262144 262144 4 5 6
22 500 262144 262144 5 6
23 500 262144 262144 5 6
24 500 262144 262144 5 6
25 500 262144 262144 5 6
26 500 262144 262144 5 6
27 500 262144 262144 5 6
28 500 32768 262144 6
29 500 32768 262144 6
30 500 32768 262144 6
31 500 32768 262144 6
32 500 32768 262144 6
33 500 32768 262144 6
34 500 32768 262144 6
35 500 32768 262144 6