No.2535 Multiple Equivalence
Problem Statement
Here, a propositional variable means a string consisting of $P$ with a positive integer subscript. For example, $P_1$ is a propositional variable, but $P$ and $Q_2$ are not propositional variables.
For each pair of integers $\ell, r$ satisfying $1 \leq \ell \leq r$, define the proposition $X(\ell,r)$ by the following recurrence:
$\displaystyle X(\ell,r) = \left\{ \begin{array}{ll} \displaystyle P_{\ell} &\displaystyle (\ell = r) \\ \displaystyle P_{\ell} \Leftrightarrow X(\ell+1,r) &\displaystyle (\ell < r) \end{array} \right. $
Here, $\Leftrightarrow$ is the logical operator representing equivalence, and for propositions $a$ and $b$, $a \Leftrightarrow b$ is defined as "if $a$ then $b$, and if $b$ then $a$".
In short, the above recurrence constructs a new proposition by associating $\Leftrightarrow$ from the right.
For example, $X(3,4)$ is the proposition $P_3 \Leftrightarrow P_4$, and $X(2,4)$ is $P_2 \Leftrightarrow X(3,4)$, that is, $P_2 \Leftrightarrow (P_3 \Leftrightarrow P_4)$.
The input gives a positive integer $N$ and a truth assignment of $P_i$ for each positive integer $i$ not exceeding $N$.
Here is an explanation for those unfamiliar with truth assignments of propositional variables. (Click to open)
A truth assignment of $P_i$ for each positive integer $i$ not exceeding $N$ is, roughly speaking, a correspondence that determines for each positive integer $i$ whether $P_i$ is true or false.
More formally, it is a map from the set of all positive integers not exceeding $N$ to $\{0,1\}$, but anyone who is comfortable with that formulation does not need this note, so we keep to the rough explanation.
Under the truth assignment given in the input, determine the truth value of the proposition $X(1,r)$ for each positive integer $r$ not exceeding $N$.
Input
The input is given from standard input in $1+N$ lines in the following format:
- Line $1$ contains $N$.
- For each positive integer $i$ not exceeding $N$, line $1+i$ contains
Yesif $P_i$ is assigned true, andNoif $P_i$ is assigned false.
$N$ $P_1$ の真偽(Yes/No) $\vdots$ $P_N$ の真偽(Yes/No)
Constraints
The input satisfies the following constraints:
- $N$ is an integer satisfying $1 \leq N \leq 10^5$.
Output
For each positive integer $r$ not exceeding $N$, print on line $r$ Yes if $X(1,r)$ is true under the truth assignment given in the input, and No if it is false.
Print a newline at the end.
Sample
Sample 1
Input
1 Yes
Output
Yes
$X(1,1)$ is $P_1$, and $P_1$ is true.
Sample 2
Input
2 No Yes
Output
No No
$X(1,1)$ is $P_1$, and $P_1$ is false.
$X(1,2)$ is $P_1 \Leftrightarrow X(2,2)$, and $X(2,2)$ is $P_2$. Since $P_2$ is true, the truth value of $P_1 \Leftrightarrow X(2,2)$ coincides with the truth value of $P_1$, and since $P_1$ is false, $X(1,2)$ is false.
Sample 3
Input
2 Yes No
Output
Yes No
$X(1,1)$ is $P_1$, and $P_1$ is true.
$X(1,2)$ is $P_1 \Leftrightarrow X(2,2)$, and $X(2,2)$ is $P_2$. Since $P_2$ is false, the truth value of $P_1 \Leftrightarrow X(2,2)$ coincides with the truth value of the negation of $P_1$, and since $P_1$ is true, $X(1,2)$ is false.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。