問題一覧 > 通常問題

No.1820 NandShift

レベル : / AI推定難易度 : 1150 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : （AC するまで非表示） / 解いたユーザー数 36
作問者 : nok0 / テスター : zkou Kite_kuma riano
お気に入りにしたユーザー ProblemId : 6932 / 自分の提出
問題文最終更新日: 2022-01-14 23:17:47
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 contest 328 (順位表) の他の問題:

Problem Statement

There is a sequence of $M$-bit integers $B = (B_0,B_1,B_2,\dots,B_{10^9})$ of length $10^9 + 1$.

Initially, $B_i = A_i$ for $1\le i \le N$, and $B_i = 0$ for $i = 0$ and $N < i \le 10^9$.

zkou's goal is to finally make $B_{0} = X$.

zkou can perform the following operations in any order, up to $1000$ times. (Here, $0\le x,i,j \le 10^9$.)

  • 1 x i: Replace $B_x$ with $2B_i \bmod 2^M$.
  • 2 x i j: Replace $B_x$ with $B_i\ \mathrm{bitwise\ nand}\ B_j$.

Determine whether zkou can achieve the goal, and if so, show one example of a sequence of operations.


Here, $x\ \mathrm{bitwise\ nand}\ y $ is defined as follows.

  • In the binary representation of $x\ \mathrm{bitwise\ nand}\ y $, the digit in the $2^k(0\le k < M)$ place is $0$ if the digits in the $2^k$ place of $x,y$ are both $1$, and $1$ otherwise.
  • In the binary representation of $x\ \mathrm{bitwise\ nand}\ y $, the digits in the $2^k(M \le k)$ places are all $0$.

    • Constraints

    • All inputs are integers.
    • $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$ are given in binary notation of length $M$.

    Input

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

    Output

    If the goal cannot be achieved, output only -1.

    If the goal can be achieved, first output the number of operations $K$ followed by a newline. Here, $K$ must satisfy $1 \le K \le 1000$.

    Then, over the following $K$ lines, output the operations in the format 1 x i or 2 x i j.

    Sample

    Sample 1
    Input
    2 3
111
001
011
    Output
    3
1 2 2
1 2 2
2 0 1 2

    The above output satisfies the conditions. The process is shown below.

    • Initially, $B_0 = 0, B_1 = 1,B_2 = 3,B_3 = B_4 = \dots = B_{10^9} = 0$.
    • 1 2 2 makes $B_2 = 2B_2\bmod 2^3 = 6$.
    • 1 2 2 makes $B_2 = 2B_2\bmod 2^3 = 4$.
    • 2 0 1 2 makes $B_0 = B_1\ \mathrm{bitwise\ nand}\ B_2 = 7$.
    • In the end, $B_0 = 7$ holds, which is zkou's goal.

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