No.8074 5000000000000000-SAT
タグ : / 解いたユーザー数 219
作問者 : stoq / テスター : nok0
問題文
$5000000000000000$ 個の変数 $x_1, x_2, \dots, x_{5000000000000000}$ があります。
$x_1, x_2, \dots, x_{5000000000000000}$ にそれぞれ真または偽を割り当てることで、論理式 $f(x_1, x_2, \dots, x_{5000000000000000})$ を真にできるでしょうか?
ただし $f(x_1, x_2, \dots, x_{5000000000000000})$ は次のように定義します。
$\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} )$
入力
$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$
出力
条件を満たす割り当てが存在するならばYes
を、存在しないならばNo
を出力してください。
サンプル
サンプル1
入力
2 1 1 2 2
出力
Yes
$f(x_1, x_2, \dots, x_{5000000000000000}) = x_1 \wedge x_2$ なので、$x_1 = x_2 = 1$ でさえあればよいです。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。