TopCoder

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

User's AC Ratio

50.0% (1/2)

Submission's AC Ratio

83.3% (5/6)

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

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