No.1734 Decreasing Elements

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 29
作問者 :

platinum / テスター :

sak

8 ProblemId : 6775 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2021-08-25 19:25:10

$N$ 項からなる非負整数列 $A = (A_{1}, A_{2}, \dots, A_{N})$ があります。すべての $i = 1, 2, \dots, N$ に対して $A_{i} = 0$ となるまで、高橋君は以下の操作を繰り返し行います。

操作：

$i = 1, 2, \dots, N$ のうち、 $A_{i} > 0$ を満たす最小の $i$ を $j$ とする。このときの $A_{j}$ の値を $K$ とする。
$i = j, j + 1, \dots, N$ それぞれに対して、 $A_{i} \geq K$ であれば $A_{i}$ を $A_{i} - K$ に置き換える。そうでなければ何もしない。

この操作は有限回で終了することが証明できます。高橋君が操作を行う回数を求めてください。

 $N$ 
 $A_{1} A_{2} \dots A_{N}$

答えを一行に出力してください。

3
3 1 4

操作により数列 $A$ は以下のように変化します。
$(3, 1, 4)$ → $(0, 1, 1)$ → $(0, 0, 0)$
したがって求めるべき答えは $2$ です。

1
0

はじめから全ての要素が $0$ であれば一度も操作を行いません。

17
1 0 54 21 87 79 79 82 12 28 41 2 53 26 22 80 19

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