No.2090 否定論理積と充足可能性
タグ : / 解いたユーザー数 106
作問者 : 👑
p-adic
/ テスター :
taiga0629kyopro
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. Show the original
Problem Statement
You are given non-negative integers $A_0,A_1,A_2,A_3,A_4,A_5$ as input.
First, we explain the notation.
Here, a symbol consisting of $P$ with a non-negative integer subscript denotes a propositional variable. For example, $P_0$ and $P_3$ are propositional variables, but $P$, $Q$, and $Q_0$ are not.
$(\mid)$ is the Sheffer stroke, which denotes negative conjunction (NAND).
Determine whether the propositional formula
$\displaystyle (((P_{A_0} \mid P_{A_1}) \mid P_{A_2}) \mid ((P_{A_3} \mid P_{A_4}) \mid P_{A_5})) $
is satisfiable.
Below is a supplementary explanation of the terminology for those not familiar with propositional logic. (Click to open)
A truth assignment of propositional variables is, roughly speaking, a correspondence that determines, for each non-negative integer $i$, whether $P_i$ is true or false.
More formally, it is a map from the set $\mathbb{N}$ of all non-negative integers to $\{0,1\}$, but anyone comfortable with that formulation does not need this supplement, so we keep to the rough explanation.
A propositional formula $F$ is satisfiable if there exists a truth assignment of propositional variables under which $F$ is true. For example, the formula
$\displaystyle P_0 \land (P_1 \lor P_0) $
is satisfiable, since the whole formula becomes true when all propositional variables (although those from $P_2$ onward are irrelevant) are set to true. On the other hand, the formula
$\displaystyle P_0 \land (\neg P_0) $
is not satisfiable. Indeed, if $P_0$ is true, the subformula $\neg P_0$ on the right of $\land$ is false, so the whole formula is false; if $P_0$ is false, the subformula $P_0$ on the left of $\land$ is false, so the whole formula is again false. Thus the whole formula is false no matter which truth assignment of propositional variables is chosen.
Input
The input is given from standard input in the following format:
$A_0$ $A_1$ $A_2$ $A_3$ $A_4$ $A_5$
$A_0,A_1,A_2,A_3,A_4,A_5$ are given on $1$ line, separated by single-byte spaces.
Constraints
The input $A_0, A_1, A_2, A_3, A_4, A_5$ satisfies the following constraints:
- $A_0$ is a non-negative integer less than or equal to $10^{100}$
- $A_1$ is a non-negative integer less than or equal to $10^{100}$
- $A_2$ is a non-negative integer less than or equal to $10^{100}$
- $A_3$ is a non-negative integer less than or equal to $10^{100}$
- $A_4$ is a non-negative integer less than or equal to $10^{100}$
- $A_5$ is a non-negative integer less than or equal to $10^{100}$
Output
Print YES if the propositional formula
$\displaystyle (((P_{A_0} \mid P_{A_1}) \mid P_{A_2}) \mid ((P_{A_3} \mid P_{A_4}) \mid P_{A_5})) $
is satisfiable, and NO if it is not satisfiable.
Print a newline at the end.
Sample
Sample 1
Input
0 1 2 3 4 5
Output
YES
The formula whose satisfiability is to be determined is
$\displaystyle (((P_0 \mid P_1) \mid P_2) \mid ((P_3 \mid P_4) \mid P_5)) $
Under the truth assignment that sets $P_2$ to true and all the remaining propositional variables (although those from $P_6$ onward are irrelevant) to false, the whole formula is true, so this formula is satisfiable.
Sample 2
Input
0 0 1 1 2 2As shown here, the non-negative integers given in the input may contain duplicates.
Output
YES
The formula whose satisfiability is to be determined is
$\displaystyle (((P_0 \mid P_0) \mid P_1) \mid ((P_1 \mid P_2) \mid P_2)) $
Under the truth assignment that sets $P_0, P_1$ to false and all the remaining propositional variables (although those from $P_3$ onward are irrelevant) to true, the whole formula is true, so this formula is satisfiable.
Sample 3
Input
0 0 0 0 0 10As shown here, values greater than $5$ may be given in the input.
Output
YES
The formula whose satisfiability is to be determined is
$\displaystyle (((P_0 \mid P_0) \mid P_0) \mid ((P_0 \mid P_0) \mid P_{10})) $
Under the truth assignment that sets $P_0$ to false and all the remaining propositional variables (although those other than $P_{10}$ are irrelevant) to true, the whole formula is true, so this formula is satisfiable.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。