問題一覧 > 通常問題

No.2142 Segment Zero

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 132
作問者 : milkcoffee / テスター : nok0 遭難者
7 ProblemId : 8642 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-11-25 22:32:42

問題文

長さ NN の整数列 AA があり、はじめは Ai=iA_i=i 、つまり A=(1,2,...,N)A=(1,2,...,N) となっています。あなたは以下の操作を行うことができます。

  • 整数 l,r (1≤l≤r≤N)l,r \ (1 \leq l \leq r \leq N) を選び、 Al,Al+1,⋯ ,ArA_l, A_{l+1}, \cdots , A_r それぞれの値を 00 に置き換える。

AA の要素の和を KK にするために必要な操作回数の最小値を求めてください。

入力

NN KK

  • 1≤N≤1061 \leq N \leq 10^6
  • 0≤K<N(N+1)20 \leq K < \frac{N(N+1)}{2}
  • 入力は全て整数である

出力

AA の要素の和を KK にするために必要な操作回数の最小値を整数で出力してください。

サンプル

サンプル1
入力
5 7
出力
2

はじめ、A=(1,2,3,4,5)A=(1,2,3,4,5) です。
まず、l=1,r=2l=1,r=2 として操作をすると A=(0,0,3,4,5)A=(0,0,3,4,5) となります。
次に、l=5,r=5l=5,r=5 として操作をすると A=(0,0,3,4,0)A=(0,0,3,4,0) となります。
22 回の操作で AA の要素の和を 77 にすることができました。

サンプル2
入力
1000000 1000001
出力
1

l=2,r=999999l=2,r=999999 として操作をすれば良いです。

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