問題一覧 > 教育的問題

No.2121 Membership Relation and Satisfiability

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

Problem Statement

You are given as input a non-negative integer $N$ not exceeding $5$ and non-negative integers $A_0, A_1, A_2, A_3, A_4, A_5$ not exceeding $2$.

 

Here, set variables are denoted by the symbol $x$ with a non-negative integer as a subscript.

For example, $x_0$ and $x_3$ are set variables, but $x$, $y$, and $y_0$ are not set variables.

 

First, let us review the notation. For each non-negative integer $n$, the finite set $V_n$ is defined recursively as follows:

  • If $n = 0$, then $V_n$ is the empty set.
  • If $n > 0$, then $V_n$ is the power set of $V_{n-1}$, that is, the set of all subsets of $V_{n-1}$.
For example, by definition, $V_0 = \{\}$. Since the only subset of $\{\}$ is $\{\}$ itself, $V_1$ is the set $\{\{\}\}$, whose only element is $\{\}$. Since $\{\{\}\}$ has two subsets, $\{\}$ and $\{\{\}\}$ itself, $V_2$ is the set $\{\{\},\{\{\}\}\}$, whose only elements are $\{\}$ and $\{\{\}\}$.

 

Determine whether the set-theoretic formula

$\displaystyle ((((\forall x_3((x_3 \in x_{A_0}) \to (x_3 \in x_{A_1}))) \land (x_{A_1} \in x_{A_2})) \land (x_{A_3} \in x_{A_2})) \land (x_{A_4} \in x_{A_2})) \land (x_{A_5} \in x_{A_0}) $

is satisfiable in $V_N$, that is, whether there exists a combination $(m_0,m_1,m_2)$ of elements $m_0, m_1, m_2$ of $V_N$ for which the formula

$\displaystyle ((((\forall x_3 \in V_N((x_3 \in m_{A_0}) \to (x_3 \in m_{A_1}))) \land (m_{A_1} \in m_{A_2})) \land (m_{A_3} \in m_{A_2})) \land (m_{A_4} \in m_{A_2})) \land (m_{A_5} \in m_{A_0}) $

is true.

Be careful not to confuse $m_3$ with $m_{A_3}$.

 

Below is an explanation for those who are not familiar with $\forall$. (Click to open)

 

Given a formula $P$, the formula $\forall x_3(P)$ is read in words as follows:

  • For any $x_3$, $P$ holds.
  • For every $x_3$, $P$ holds.

In other words, no matter how $x_3$ is chosen, $P$ always holds. For example, $\forall x_3(x_3 = x_3)$ is read as follows:

  • For any $x_3$, $x_3 = x_3$ holds.
  • For every $x_3$, $x_3 = x_3$ holds.

and so on.

Furthermore, given a set $M$, if we want to restrict the range of $x_3$ to $M$, we write $\forall x_3 \in M(P)$. This is read in words as follows:

  • For any element $x_3$ of $M$, $P$ holds.
  • For any $x_3$ belonging to $M$, $P$ holds.
  • For every element $x_3$ of $M$, $P$ holds.
  • For every $x_3$ belonging to $M$, $P$ holds.

and so on. Note that the notation $\forall x_3 \in M(P)$ is actually syntactic sugar for $\forall x_3(x_3 \in M \to P)$, so following that definition, it may also be read as follows:

  • For any element $x_3$, if $x \in M$ then $P$ holds.
  • For every $x_3$, if $x \in M$ then $P$ holds.

and so on. In this problem, we take $V_N$ as $M$ and deal with formulas of the form $\forall x_3 \in V_N(P)$.

 

Input

The input is given from standard input in the following format:

$N$
$A_0$ $A_1$ $A_2$ $A_3$ $A_4$ $A_5$

The $1$st line contains $N$, and the $2$nd line contains $A_0, A_1, A_2, A_3, A_4, A_5$ separated by single-byte spaces.

Constraints

The input $N, A_0, A_1, A_2, A_3, A_4, A_5$ satisfies the following constraints:

  • $N$ is a non-negative integer not exceeding $5$
  • $A_0$ is a non-negative integer not exceeding $2$
  • $A_1$ is a non-negative integer not exceeding $2$
  • $A_2$ is a non-negative integer not exceeding $2$
  • $A_3$ is a non-negative integer not exceeding $2$
  • $A_4$ is a non-negative integer not exceeding $2$
  • $A_5$ is a non-negative integer not exceeding $2$

Output

If the set-theoretic formula

$\displaystyle ((((\forall x_3((x_3 \in x_{A_0}) \to (x_3 \in x_{A_1}))) \land (x_{A_1} \in x_{A_2})) \land (x_{A_3} \in x_{A_2})) \land (x_{A_4} \in x_{A_2})) \land (x_{A_5} \in x_{A_0}) $

is satisfiable in $V_N$, print YES; otherwise, print NO.

Print a newline at the end.

Sample

Sample 1
Input
1
0 0 0 0 0 0
Output
NO

Here, $x_{A_0},x_{A_1},x_{A_2},x_{A_3},x_{A_4},x_{A_5}$ are all $x_0$, so the formula whose satisfiability must be determined is

$\displaystyle ((((\forall x_3((x_3 \in x_0) \to (x_3 \in x_0))) \land (x_0 \in x_0)) \land (x_0 \in x_0)) \land (x_0 \in x_0)) \land (x_0 \in x_0) $

. Since $N = 1$, we need to consider satisfiability in $V_1 = \{\{\}\}$. Since $V_1$ has no element other than $\{\}$, the only possible choice is to set all of $m_0,m_1,m_2$ to $\{\}$. However, the formula corresponding to this choice,

$\displaystyle ((((\forall x_3 \in V_1((x_3 \in \{\}) \to (x_3 \in \{\}))) \land (\{\} \in \{\})) \land (\{\} \in \{\})) \land (\{\} \in \{\})) \land (\{\} \in \{\}) $

, is false as a whole, because the subformula $\{\} \in \{\}$ on the right side of the $1$st $\land$ is false. Therefore, the given formula is not satisfiable in $V_N$.

Sample 2
Input
3
0 0 1 0 0 2
Output
YES

Here, $x_{A_0},x_{A_1},x_{A_3},x_{A_4}$ are $x_0$, $x_{A_2}$ is $x_1$, and $x_{A_5}$ is $x_2$, so the formula whose satisfiability must be determined is

$\displaystyle ((((\forall x_3((x_3 \in x_0) \to (x_3 \in x_0))) \land (x_0 \in x_1)) \land (x_0 \in x_1)) \land (x_0 \in x_1)) \land (x_2 \in x_0) $

. Since $N = 3$, we need to consider satisfiability in $V_3$. For that, we must consider what elements exist in $V_3$.

 

First, since $V_2 = \{\{\},\{\{\}\}\}$, we have

$\displaystyle \begin{array}{rcl} \displaystyle \{\} &\displaystyle \subset &\displaystyle V_2 \\ \displaystyle \{\{\}\} &\displaystyle \subset &\displaystyle V_2 \\ \displaystyle \{\{\},\{\{\}\}\} &\displaystyle \subset &\displaystyle V_2 \\ \end{array} $

. Hence, by the definition of $V_3$, all of $\{\}$, $\{\{\}\}$, and $\{\{\},\{\{\}\}\}$ are elements of $V_3$. So, for example, if we set $m_0$ to the element $\{\{\}\}$ of $V_3$, $m_1$ to the element $\{\{\},\{\{\}\}\}$ of $V_3$, and $m_2$ to the element $\{\}$ of $V_3$, then the corresponding formula

$\displaystyle ((((\forall x_3 \in V_3((x_3 \in \{\{\}\}) \to (x_3 \in \{\{\}\}))) \land (\{\{\}\} \in \{\{\},\{\{\}\}\})) \land (\{\{\}\} \in \{\{\},\{\{\}\}\})) \land (\{\{\}\} \in \{\{\},\{\{\}\}\})) \land (\{\} \in \{\{\}\}) $

is true. Indeed, the formulas $\{\} \in \{\{\}\}$ and $(\{\{\}\} \in \{\{\},\{\{\}\}\})$ on the right sides of the $4$ occurrences of $\land$ are true, so it suffices to verify that the formula on the left side of the $1$st $\land$,

$\displaystyle \forall x_3 \in V_3((x_3 \in \{\{\}\}) \to (x_3 \in \{\{\}\})) $

, is true. The formula within the scope of $\forall x_3 \in V_3$,

$\displaystyle (x_3 \in \{\{\}\}) \to (x_3 \in \{\{\}\}) $

, has identical antecedent (the formula on the left of "implies") and consequent (the formula on the right of "implies"), so it is true no matter how $x_3$ is chosen. In particular, the formula obtained by applying $\forall x_3 \in V_N$ to it is also true. Therefore, the given formula is satisfiable in $V_N$.

Sample 3
Input
0
0 0 1 0 0 2
Output
NO

Here, as in Sample 2, $x_{A_0},x_{A_1},x_{A_3},x_{A_4}$ are $x_0$, $x_{A_2}$ is $x_1$, and $x_{A_5}$ is $x_2$, so the formula whose satisfiability must be determined is

$\displaystyle ((((\forall x_3((x_3 \in x_0) \to (x_3 \in x_0))) \land (x_0 \in x_1)) \land (x_0 \in x_1)) \land (x_0 \in x_1)) \land (x_2 \in x_0) $

. Since $N = 0$, we need to consider satisfiability in $V_0 = \{\}$. However, since $\{\}$ has no elements, there is no combination $(m_0,m_1,m_2)$ of $3$ elements $m_0,m_1,m_2$ of it. Therefore, the given formula is not satisfiable in $V_N$.

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