問題一覧 > 通常問題

No.2545 Divide by 3

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 32
作問者 : Shirotsume / テスター : 👑 Nachia kaichou243
8 ProblemId : 9902 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-11-24 22:15:03

問題文

この問題はoutput-onlyです。

長さ N=100N = 100 の数列 A=(A1,A2,…,AN)A = (A_1, A_2, \dots, A_N) があります。初め、 A1=X,A2=1A_1 = X, A_2 = 1 であり、i≥3i \geq 3 について、Ai=0A_i = 0 です。ただし、XX は 0≤X≤1090 \leq X \leq 10^9 を満たす非負整数で、入力には与えられません。

あなたは、次に示す操作を 10001000 回まで行うことができます。ただし、i,j,ki, j, k は 1≤i,j,k≤N1 \leq i, j, k \leq N を満たす整数です。

  • plus i j k: Ai←Aj+AkA_i \leftarrow A_j + A_k とする。
  • div i j: Ai←⌊Aj2⌋\displaystyle A_i \leftarrow \left \lfloor \frac{A_j}{2} \right \rfloor とする。

ただし、操作のいかなる瞬間においても、AiA_i が 2642^{64} 以上となってはいけません。

あなたの目標は全ての操作を実行した後、A3=⌊X3⌋\displaystyle A_3 = \left \lfloor \frac{X}{3} \right \rfloor とすることです。これを達成できる操作列をひとつ出力してください。

入力

入力は与えられない。

出力

出力の 11 行目には、操作を行う回数 MM (0≤M≤1000)(0 \leq M \leq 1000) を出力せよ。

22 行目から MM 行にわたって行う操作を出力せよ。i+1i + 1 行目には ii 回目に行う操作を問題文の形式に従って出力せよ。

ジャッジ

提出された操作列が問題文および出力で述べられている形式に従っていない場合、ジャッジ結果は不定である。

提出された操作列の形式が正しい場合、ジャッジプログラムはテストケースごとにあらかじめ定められた 10410^4 個の整数 XX に対して、独立に操作列を実行する。

すべての XX に対し操作列を実行した結果、操作のいかなる時点でも AiA_i が 2642^{64} 以上とならず、かつ全ての操作を実行した後に A3=⌊X3⌋\displaystyle A_3 = \left \lfloor \frac{X}{3} \right \rfloor を満たしている場合、ジャッジの判定は AC となる。そうでない場合 WA と判定される。

サンプル

正しい形式の操作列の一例を示します。この例は X=3X = 3 のケースでにおいて、操作後に A3=4A_3 = 4 となるため条件を満たさず不正解となります。

5
plus 3 1 2
plus 4 4 4
div 5 3
div 5 2
plus 100 2 5

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