問題一覧 > 通常問題

No.3184 Make Same

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 76
作問者 : 蜜蜂 / テスター : Mitarushi
ProblemId : 12360 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2025-06-15 12:53:52

問題文

長さ $N$ の非負整数列 $A = (A_1, A_2, \cdots, A_N)$ が与えられます．ここで，$A$ は広義単調増加であることが保証されます．
あなたの目標は $A$ の要素をすべて同じにすることです．そのために，以下の操作を $30$ 回まで行うことができます．

  • $1 \leq l \leq r \leq N, 0 \leq v \leq 10^9$ を満たす $3$ つの整数 $l, r, v$ を宣言する．
  • その後，$i = l, l + 1, \cdots, r$ について $A_i$ を $A_i + v$ で置き換える．
  • 最後に，$A$ を昇順に並び替える．
制約下であなたの目標は必ず達成できることが証明できます．目標を達成する操作列の一例を出力してください．なお，操作の回数を最小化する必要はありません．

入力

$N$
$A_1\ \ A_2\ \ \cdots A_N$

  • $1 \leq N \leq 2 \times 10^5$
  • $0 \leq A_i \leq 10^9$
  • $A_i \leq A_{i + 1}$
  • 入力はすべて整数

出力

$M$ 回の操作で目標を達成できる場合，まず $1$ 行目に $M$ を出力してください．
その後，$M$ 行出力してください．$i$ 行目には $i$ 回目の操作で宣言する $l, r, v$ を空白区切りで出力してください．

サンプル

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

  • $1$ 回目の操作の後，$A = (1, 6, 7, 8)$ となります．
  • $2$ 回目の操作の後，$A = (6, 7, 7, 8)$ となります．
  • $3$ 回目の操作の後，$A = (7, 7, 8, 8)$ となります．
  • $4$ 回目の操作の後，$A = (8, 8, 8, 8)$ となります．

サンプル2
入力
1
0
出力
0

最初から目標が達成されている場合，操作回数を $0$ 回としても構いません．

サンプル3
入力
3
1 2 3
出力
4
3 3 997
1 1 999
1 1 998
1 3 0

最終的に $A = (1000, 1000, 1000)$ となります．

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