問題文
0からn−1までの数字が1つずつ書かれた合計n枚のカードがあります。この中から異なるk枚を選ぶ方法の中で、k枚に書かれた数字の中の最大値と最小値の差がdとなるような物の数をNdとします。Ndが最大となるようなdを求めなさい。
制約
- 2≤k≤n≤109
- 入力は全て整数
入力
入力は以下の形式で与えられます。
出力
dの値を1行に出力しなさい。ただし、Ndの値が最大となるdが複数存在する場合には、それら全てを小さい順にスペース区切りで出力しなさい。
サンプル
カードの選び方は4C2=6通りであり、そのうち
- d=1となる選び方は{0,1},{1,2},{2,3}の3通りなので、N1=3
- d=2となる選び方は{0,2},{1,3}の2通りなので、N2=2
- d=3となる選び方は{0,3}の1通りなので、N3=1
よって、Ndが最大の時d=1となります。
Ndが最大となるようなdの値は1つとは限りません。
0〜9が1枚ずつ選択されるので、d=9−0=9となります。