No.8074 5000000000000000-SAT
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もしくは右上の雲マークをクリックしてアカウントを作成してください。
stoq
nok0