問題一覧 > 通常問題

No.2308 [Cherry 5th Tune B] Could It Be True?

レベル : / AI推定難易度 : 1300 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 60
作問者 : 👑 Kazun / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 5202 / 自分の提出
問題文最終更新日: 2023-05-19 20:41:03
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 389 (Until that day when "Cherry Month" is over.) (順位表) の他の問題:

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 True or False $\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})$
    Therefore, the answer is true, so you must print True.
  • [Test case $3$]: Note that $F \to T, F \to F$ are true.

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。