問題一覧 > 通常問題

No.3211 NAND Oracle

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 72
作問者 : 👑 loop0919 / テスター : lif4635 yuusaan Cafe1942
ProblemId : 12312 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-07-25 23:15:13

問題文

ループさんは $0$ または $1$ からなる長さ $2$ の数列 $A = (A_1, A_2)$ を隠し持っています。この $A$ は入力から与えられないことに注意してください。
あなたは $A$ に対し、以下の操作をちょうど $Q$ 回繰り返します。ここで、$n$ は各操作の直前における $A$ の長さを表します。

  • $1 \leq i \lt j \leq n$ を満たす整数の組 $(i, j)$ を選ぶ。 $A$ の末尾に $A_i ~\overline{\land}~ A_j$ を挿入する。

ここで否定論理積 $\overline{\land}$ は、次を満たす二項演算であると定義されます。

  • $0 ~ \overline{\land} ~ 0 = 0 ~ \overline{\land} ~ 1 = 1 ~ \overline{\land} ~ 0 = 1$
  • $1 ~ \overline{\land} ~ 1 = 0$

ループさんの隠し持っている $A$ がいかなるものであっても、操作後の $A$ の総和が $K$ 以下となるような操作が存在するか判定してください。
存在するとき、その操作を $1$ つ提示してください。

制約

  • $1 \leq Q \leq 2 \times 10^5$
  • $2 \leq K \leq Q + 2$
  • $Q, K$ は整数

入力

入力は以下の形式で標準入力から与えられます。

$Q$ $K$

出力

題意を満たす操作が存在するとき Yes 、存在しないとき No を出力してください。

さらに Yes であった場合、改行した後以下の形式で操作を出力してください。

$i_1$ $j_1$
$i_2$ $j_2$
$\vdots$
$i_Q$ $j_Q$

ここで、$i_k, j_k$ は $k$ 回目 $(1 \leq k \leq Q)$ の操作で選ぶ $i, j$ を表します。

正答が複数存在する場合、そのいずれを出力しても正解と判定されます。

サンプル

サンプル1
入力
3 3
出力
Yes
1 2
2 3
1 4

例えば、ループさんが $A = (1, 0)$ を隠し持っていた場合、以下の流れで操作が進みます。

  • $(i, j) = (1, 2)$ を選ぶ。$1 ~ \overline{\land} ~ 0 = 1$ であるため、$A$ は $(1, 0, 1)$ に更新される。
  • $(i, j) = (2, 3)$ を選ぶ。$0 ~ \overline{\land} ~ 1 = 1$ であるため、$A$ は $(1, 0, 1, 1)$ に更新される。
  • $(i, j) = (1, 4)$ を選ぶ。$1 ~ \overline{\land} ~ 1 = 0$ であるため、$A$ は $(1, 0, 1, 1, 0)$ に更新される。

このとき、$A$ の総和は $3$ であり、$K = 3$ 以下となります。これは、ループさんがはじめにどのような $A$ を隠し持っていても成り立つことが示せます。

サンプル2
入力
4 2
出力
No

$Q = 4, ~ K = 2$ のとき、条件を満たす操作が存在しません。

サンプル3
入力
9 6
出力
Yes
1 2
1 2
1 2
1 2
3 4
3 5
3 6
4 5
7 8

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