問題一覧 > 通常問題

No.2142 Segment Zero

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 112
作問者 : milkcoffeemilkcoffee / テスター : 遭難者遭難者 nok0nok0
7 ProblemId : 8642 / 出題時の順位表 / 自分の提出
問題文最終更新日: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。