No.2308 [Cherry 5th Tune B] Could It Be True?
Problem Statement
You are given a sequence $E$ in which $N$ propositional constants $A_1, \dots, A_N$ and $(N-1)$ logical operators $\operatorname{op}_1, \dots, \operatorname{op}_{N-1}$ appear alternately as follows. $$E: (A_1, \operatorname{op}_1, A_2, \operatorname{op}_2, A_3, \dots, A_{N-2}, \operatorname{op}_{N-2}, A_{N-1}, \operatorname{op}_{N-1}, A_N)$$
Here, each of the $N$ propositional constants $A_i$ is given by a string $X_i$, with the following meaning.
- If $X_i$=
True, then $A_i$ is true. - If $X_i$=
False, then $A_i$ is false.
Likewise, each of the $(N-1)$ logical operators $\operatorname{op}_i$ is given by a string $Y_i$, with the following meaning.
- If $Y_i$=
and, then $\operatorname{op}_i$ is the logical conjunction $\land$. - If $Y_i$=
or, then $\operatorname{op}_i$ is the logical disjunction $\lor$. - If $Y_i$=
xor, then $\operatorname{op}_i$ is the exclusive disjunction $\veebar$. - If $Y_i$=
imp, then $\operatorname{op}_i$ is the implication $\to$.
The following operation is performed $(N-1)$ times on this sequence $E$. Here, the $j~(1 \leq j \leq N-1)$-th operation is described by an integer $S_j$.
- In $E$, delete the contiguous subsequence of length $3$ starting at the $S_j$-th propositional constant, $(A_{S_j}, \operatorname{op}_{S_j}, A_{S_j+1})$, and insert the result of $A_{S_j} \operatorname{op}_{S_j} A_{S_j+1}$ at the position where it was. (Then, if necessary, the indices of the propositional constants and of the logical operators are each renumbered starting from $1$.)
After performing the operation $(N-1)$ times, $E$ becomes a sequence consisting of only $1$ propositional constant. Now, is that only $1$ propositional constant true? Or is it false?
Solve $T$ test cases.
Notes
Let $P,Q$ be propositional constants.
- The logical conjunction of $P,Q$, written $P \land Q$, is defined to be true if both $P,Q$ are true, and false otherwise.
- The logical disjunction of $P,Q$, written $P \lor Q$, is defined to be true if at least one of $P,Q$ (possibly both) is true, and false otherwise.
- The exclusive disjunction of $P,Q$, written $P \veebar Q$, is defined to be true if the truth values of $P,Q$ differ, and false otherwise.
- The implication of $P,Q$, written $P \to Q$, is defined to be $Q$ if $P$ is true, and true if $P$ is false.
Constraints
- $1 \leq T \leq 10^5$.
- $T$ is an integer.
- Constraints for each test case
- $2 \leq N$.
- $X_i$ is
TrueorFalse$\quad (1 \leq i \leq N)$. - $Y_i$ is one of
and,or,xor,imp$\quad (1 \leq i \leq N-1)$. - $1 \leq S_j \leq N-j \quad (1 \leq j \leq N-1)$.
- $N, S_j$ are integers.
- Constraints for each test file
- The sum of $N$ over the $T$ test cases is at most $2 \times 10^5$.
Do not forget the newline at the end.
Input
The input is given from standard input in the following format.$T$
$\text{Testcase}_1$
$\text{Testcase}_2$
$\vdots$
$\text{Testcase}_T$
Each test case is in the following format.
$N$
$X_1$ $X_2$ $\cdots$ $X_{N-1}$ $X_N$
$Y_1$ $Y_2$ $\cdots$ $Y_{N-1}$
$S_1$ $S_2$ $\cdots$ $S_{N-1}$
Output
The output consists of $T$ lines.
On line $t$, for test case $t$, print True if the answer is true, and False if it is false.
Sample
Sample 1
Input
3 5 True False True False True and or xor imp 2 2 1 1 3 False True False and and 1 1 4 False True False False imp and imp 1 2 1
Output
True False True
In this explanation, let $T,F$ be the propositional constants representing true and false, respectively.
- [Test case $1$]: The operations change $E$ as follows. The parts changed by each operation are underlined.
- From $(T, \land, \underline{F, \lor, T}, \veebar, F, \to, T)$ to $(T, \land, \underline{T}, \veebar, F, \to, T)$
- From $(T, \land, \underline{T, \veebar, F}, \to, T)$ to $(T, \land, \underline{T}, \to, T)$
- From $(\underline{T, \land, T}, \to, T)$ to $(\underline{T}, \to, T)$
- From $(\underline{T, \to, T})$ to $(\underline{T})$
True. - [Test case $3$]: Note that $F \to T, F \to F$ are true.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
Kazun