問題一覧 > ネタ問題

No.8074 5000000000000000-SAT

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 239
作問者 : stoq / テスター : nok0
お気に入りにしたユーザー ProblemId : 6067 / 自分の提出
問題文最終更新日: 2021-03-10 09:22:40
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 April Fool Contest 2021 (順位表) の他の問題:

Problem Statement

There are $5000000000000000$ variables $x_1, x_2, \dots, x_{5000000000000000}$.
Is it possible to make the logical formula $f(x_1, x_2, \dots, x_{5000000000000000})$ true by assigning true or false to each of $x_1, x_2, \dots, x_{5000000000000000}$?

Here, $f(x_1, x_2, \dots, x_{5000000000000000})$ is defined as follows.

$\displaystyle f(x_1, x_2, \dots, x_{5000000000000000}) := \bigwedge_{i=1}^{N} (x_{a_i} \vee x_{a_i +1} \vee \cdots \vee x_{b_i} )$

Input

$N$
$a_1\ b_i$
$\vdots$
$a_N\ b_N$

$1 \leq N \leq 10^5$
$1 \leq a_i \leq b_i \leq 5000000000000000$

Output

Print Yes if an assignment satisfying the condition exists, and No otherwise.

Sample

Sample 1
Input
2
1 1
2 2
Output
Yes

Since $f(x_1, x_2, \dots, x_{5000000000000000}) = x_1 \wedge x_2$, it suffices that $x_1 = x_2 = 1$.

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