No.2142 Segment Zero
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 130
作問者 :
milkcoffee
/ テスター :
nok0
遭難者
タグ : / 解いたユーザー数 130
作問者 :
milkcoffee
/ テスター :
nok0
遭難者
問題文最終更新日: 2022-11-25 22:32:42
問題文
長さ $N$ の整数列 $A$ があり、はじめは $A_i=i$ 、つまり $A=(1,2,...,N)$ となっています。あなたは以下の操作を行うことができます。
- 整数 $l,r \ (1 \leq l \leq r \leq N)$ を選び、 $A_l, A_{l+1}, \cdots , A_r$ それぞれの値を $0$ に置き換える。
$A$ の要素の和を $K$ にするために必要な操作回数の最小値を求めてください。
入力
$N$ $K$
- $1 \leq N \leq 10^6$
- $0 \leq K < \frac{N(N+1)}{2}$
- 入力は全て整数である
出力
$A$ の要素の和を $K$ にするために必要な操作回数の最小値を整数で出力してください。
サンプル
サンプル1
入力
5 7
出力
2
はじめ、$A=(1,2,3,4,5)$ です。
まず、$l=1,r=2$ として操作をすると $A=(0,0,3,4,5)$ となります。
次に、$l=5,r=5$ として操作をすると $A=(0,0,3,4,0)$ となります。
$2$ 回の操作で $A$ の要素の和を $7$ にすることができました。
サンプル2
入力
1000000 1000001
出力
1
$l=2,r=999999$ として操作をすれば良いです。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。