問題一覧 > 教育的問題

No.2535 Multiple Equivalence

レベル : / AI推定難易度 : 500 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 81
作問者 : 👑 p-adic / テスター : kumakuma hiro1729
お気に入りにしたユーザー ProblemId : 9507 / 自分の提出
問題文最終更新日: 2023-08-15 13:10:45
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 412 (順位表) の他の問題:

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 Yes if $P_i$ is assigned true, and No if $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もしくは右上の雲マークをクリックしてアカウントを作成してください。