TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P3083
  • 問題
  • P3083青蛙表演
    制限 : 時間制限 : 10000 MS   メモリ制限 : 165536 KB
    問題説明

    何老板训练了一只青蛙,该蛙擅长跳跃。它经常从一片荷叶跳到另一片荷叶。今天,何老板打算用N根木桩来向世人展示该蛙的跳跃技能。
    这n根木桩排成一行,蛙首先从最矮的木桩顶部起跳,总共进行N-1次跳跃。每次它只能跳到比当前木桩更高的一个木桩顶部。当表演结束时,每个木桩它都恰好到过一次,最终停在最高的木桩顶部。
    这只青蛙向上跳跃能力很强,但水平方向跳跃能力就有限了,每次跳跃,它在水平方向飞行的距离不超过D米。舞台上给出的这N根木桩的排列顺序不可改变,但木桩间的间距可以任意调整,但间距必须是整数而且至少为1,且两根木桩不能位于同一点上。何老板想知道,在成功完成表演的前提下,最矮跟最高的那根木桩的间距最大可能是多少?如果无论如何都不能完成表演,输出-1

    入力形式

    第一行,两个空格间隔的整数N和D
    第二行,N个空格间隔的整数,依次给出了每根木桩的高度,不会有相同高度的木桩,木桩的高度在int范围以内。

    出力形式

    一个整数,表示最矮和最高木桩可能的最大间距
    若不可能完成表演,输出-1

    サンプル入力 1

    样例1:
    4 4 
    20 30 10 40

    样例2:
    4 2 
    10 20 16 13

    サンプル出力 1

    样例1:
    3

    样例2:
    -1

    サンプル入力 2

    5 6
    11 2 24 27 42 

    サンプル出力 2

    17

    ヒント

    【样例解释】
    样例1说明:
    高度20和高度30的木桩的间距可以是1到3之间的任意数字
    高度30和高度10的木桩的间距为1
    高度10和高度40的木桩的间距为3
    跳跃的顺序是:
    1.从10跳到20,间距<=4
    2.从20跳到30,间距<=4
    3.从30跳到40,间距恰好为4。

    【数据范围】
    对于40%的数据 1 ≤ N ≤ 100
    对于100%的数据 1 ≤ N ≤ 1000 ,1 ≤ D ≤1000000