問題一覧 > 通常問題

No.1820 NandShift

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 35
作問者 : nok0nok0 / テスター : zkouzkou Kite_kumaKite_kuma rianoriano
2 ProblemId : 6932 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-01-14 23:17:47

問題文

長さ $10^9 + 1$ の $M$ bit 整数列 $B = (B_0,B_1,B_2,\dots,B_{10^9})$ があります。

はじめ $1\le i \le N$ について $B_i = A_i$ であり, $i = 0$ 及び $N < i \le 10^9$ について $B_i = 0$ です。

zkou 君の目的は、最終的に $B_{0} = X$ とすることです。

zkou 君は、以下の操作を好きな順番で $1000$ 回まで行うことができます。(ここで、 $0\le x,i,j \le 10^9$ です。)

  • 1 x i: $B_x$ を $2B_i \bmod 2^M$ で置き換える
  • 2 x i j: $B_x$ を $B_i\ \mathrm{bitwise\ nand}\ B_j$ で置き換える

zkou 君が目的を達成可能か判定し、達成可能な場合は実際に操作手順の一例を示してください。


ただし $x\ \mathrm{bitwise\ nand}\ y $ は以下で定義されます。

  • $x\ \mathrm{bitwise\ nand}\ y $ を二進表記した際の $2^k(0\le k < M)$ の位の数は, $x,y$ の $2^k$ の位の数が共に $1$ のとき $0$, そうでないとき $1$ とする。
  • $x\ \mathrm{bitwise\ nand}\ y $ を二進表記した際の $2^k(M \le k)$ の位の数は全て $0$ とする。

    • 制約

    • 入力は全て整数である。
    • $1 \le N \le 100$
    • $1 \le M \le 100$
    • $1 \le X < 2^M$
    • $0 \le A_i < 2^M(1\le i \le N)$
    • $X,A_i$ は長さ $M$ の2進表記で与えられる。

    入力

    $N$ $M$
$X$
$A_1$
$A_2$ 
$\vdots$
$A_N$

    出力

    目的が達成不可能な場合、-1のみを出力してください。

    目的が達成可能な場合、はじめに操作回数 $K$ を出力し改行してください。ここで $K$ は $1 \le K \le 1000$ を満たさなくてはなりません。

    その後 $K$ 行に渡って操作の方法を1 x i もしくは2 x i jの形式で出力してください。

    サンプル

    サンプル1
    入力
    2 3
111
001
011
    出力
    3
1 2 2
1 2 2
2 0 1 2

    上記の出力は条件を満たします。過程を以下で示します。

    • はじめ、 $B_0 = 0, B_1 = 1,B_2 = 3,B_3 = B_4 = \dots = B_{10^9} = 0$ である。
    • 1 2 2 により $B_2 = 2B_2\bmod 2^3 = 6$ となる。
    • 1 2 2 により $B_2 = 2B_2\bmod 2^3 = 4$ となる。
    • 2 0 1 2 により $B_0 = B_1\ \mathrm{bitwise\ nand}\ B_2 = 7$ となる。
    • 最終的に zkou 君の目的である $B_0 = 7$ を満たしている。

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