Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

ゲームバランス

あなたは冒険ゲームを作成している．このゲームのプレイヤーは，主人公を操作して敵モンスターを倒し，主人公のレベルを上げることで冒険を進めていく．主人公の初期レベルは 1 である．

このゲームには N 種類の敵モンスターが用意されており，弱い順で i 番目の種類の敵モンスターの強さは si である．主人公が 1 回の戦闘を行うときには，次に戦う敵モンスターの種類を自由に選び，ちょうど 1 体の敵モンスターと戦闘を行う．主人公は同じ種類の敵モンスターと何回でも戦うことができ，何回でも倒すことができる．

あなたはいま，このゲームのバランスを調整するために，あるパラメーター X を決めようとしている．パラメーター X は正の整数であり下記のように使われる．

 主人公のレベルが L のとき，強さ si が L+X 未満の敵は倒せるが，それより強い敵モンスターは倒せない．

 主人公のレベルが L のとき，強さ si の敵を倒すと max(1, X-|L-si|) だけ主人公のレベルが上がる．

このゲームは，最も強い（N 種類目の）敵モンスターを初めて倒したときにゲームクリアとなる．あなたは，ゲームクリアまでに必要となる戦闘の回数が最低でも M 回以上となるようにパラメーター X を決めたいと考えている．ただし，敵モンスターの強さの設定によっては，X をどのように設定しても M 回未満の戦闘回数でゲームクリアできてしまうか，ゲームをクリアできなくなってしまう場合があることに注意せよ．

パラメーター X を決めるとき，上記の条件を満たす範囲で最大のパラメーター値 Xmax を計算するプログラムを作ってほしい．

Input

入力は複数のデータセットから構成される．データセットの個数は最大でも 50 を超えない．各データセットは次の形式で表される．

N M
s1 s2 ... sN

1 行目は空白で区切られた 2 つの整数 N, M からなる．N は用意した敵モンスターの種類の数，M はゲームクリアまでに必要となるべき最小の戦闘の数であり，1 ≤ N ≤ 100,000, 2 ≤ M ≤1,000,000 を満たす．

2 行目は空白で区切られた N 個の整数 s1, s2, ..., sN からなり，N 種類の敵モンスターそれぞれの強さを表す．各 si は 1 ≤ si ≤ 1,000,000 を満たし，また si i+1 (1 ≤ i ≤ N-1) である．

入力の終わりは空白で区切られた 2 つのゼロからなる行で表される．

Output

各データセットについて，ゲームクリアまでに必要となる戦闘の回数が M 回以上となるパラメーター X の内の最大値 Xmax を整数で出力せよ．X をどのように設定しても M 回未満の戦闘回数でゲームクリアできてしまうかゲームをクリアできなくなってしまうテストケースの場合には -1 のみからなる行を出力せよ．

Sample Input

3 4
1 5 9
1 2
1
2 10
1 1000000
2 4
1 10
0 0

Output for Sample Input

3
-1
499996
4

 
    2 番目のテストケースでは，X = 1 と設定すると 1 回の戦闘でゲームをクリアできてしまう．
    このケースでは，必要となる戦闘の回数が M 回以上であり，かつゲームをクリアできるように X を設定することが出来ない．
    よって -1 のみからなる行を出力する．
    


Sample input:
3 4
1 5 9
1 2
1
2 10
1 1000000
2 4
1 10
0 0


Sample output:
3
-1
499996
4

Submission status: Wrong Answer

Solution code:
while 1:
    n, m = map(int, raw_input().split())
    if n == m == 0:
        break
    S = map(int, raw_input().split())
    left = -1; right = max(S)+2
    def check(mid):
        if 1+mid <= S[0]:
            return 10**9
        cnt = 0; l = 1
        target = S[n-1] - mid
        for i in xrange(n-1):
            while l <= S[i] and cnt <= m and l<=target:
                l += max(1, mid-(S[i]-l))
                cnt += 1
            if l+mid <= S[i+1] and cnt<=m and l<=target:
                l += max(1, mid-(l-S[i]))
                cnt += 1
                if l <= S[i+1]-mid and l<=target:
                    cnt += min(S[i+1]-mid,target)-l+1
                    l = min(S[i+1]-mid,target)+1
        return cnt
    while left+1 < right:
        mid = (left + right) / 2
        if m <= check(mid):
            left = mid
        else:
            right = mid
    if 10**8 < check(left):
        print -1
    else:
        print right

Submission status: Wrong Answer

Solution code:
while 1:
    n, m = map(int, raw_input().split())
    if n == m == 0:
        break
    S = map(int, raw_input().split())
    left = -1; right = max(S)+2
    def check(mid):
        if 1+mid <= S[0]:
            return 10**9
        cnt = 0; l = 1
        target = S[n-1] - mid
        for i in xrange(n-1):
            while l <= S[i] and cnt <= m and l<=target:
                l += max(1, mid-(S[i]-l))
                cnt += 1
            if l+mid <= S[i+1] and cnt<=m and l<=target:
                l += max(1, mid-(l-S[i]))
                cnt += 1
                if l <= S[i+1]-mid and l<=target:
                    cnt += min(S[i+1]-mid,target)-l
                    l = min(S[i+1]-mid,target)
        return cnt
    while left+1 < right:
        mid = (left + right) / 2
        if m <= check(mid):
            left = mid
        else:
            right = mid
    if 10**8 < check(left):
        print -1
    else:
        print right

Submission status: Wrong Answer

Solution code:
while 1:
    n, m = map(int, raw_input().split())
    if n == m == 0:
        break
    S = map(int, raw_input().split())
    left = 0; right = sum(S)+2
    def check(mid):
        if 1+mid <= S[0]:
            return 10**9
        cnt = 0; l = 1
        target = S[n-1] - mid
        for i in xrange(n-1):
            while l <= S[i] and cnt<=m and l<=target:
                l += mid-(S[i]-l)
                cnt += 1
            if (l+mid <= S[i+1] or abs(l-S[i]) < abs(l-S[i+1])) and cnt<=m and l<=target:
                l += mid-(l-S[i])
                cnt += 1
                if l+mid <= S[i+1]:
                    cnt += S[i+1]-mid+1-l
                    l = S[i+1]-mid+1
        return cnt
    while left+1 < right:
        mid = (left + right) / 2
        if m-1 <= check(mid):
            left = mid
        else:
            right = mid
    if 10**8 < check(left):
        print -1
    else:
        print left

Submission status: Accepted

Solution code:
while 1:
    n, m = map(int, raw_input().split())
    if n == m == 0:
        break
    S = map(int, raw_input().split())
    left = 0; right = sum(S)+2
    def check(mid):
        if 1+mid <= S[0]:
            return 10**9
        cnt = 0; l = 1
        target = S[n-1] - mid
        for i in xrange(n-1):
            while l <= S[i] and cnt<=m and l<=target:
                l += mid-(S[i]-l)
                cnt += 1
            if (l+mid <= S[i+1] or abs(l-S[i]) < abs(l-S[i+1])) and cnt<=m and l<=target:
                l += max(1, mid-(l-S[i]))
                cnt += 1
                if l+mid <= S[i+1]:
                    cnt += S[i+1]-mid+1-l
                    l = S[i+1]-mid+1
        return cnt
    while left+1 < right:
        mid = (left + right) / 2
        if m-1 <= check(mid):
            left = mid
        else:
            right = mid
    if 10**8 < check(left):
        print -1
    else:
        print left

Submission status: Runtime Error

Solution code:
while 1:
    n, m = map(int, raw_input().split())
    if n == m == 0:
        break
    S = map(int, raw_input().split())
    left = -1; right = max(S)+2
    def check(mid):
        if 1+mid <= S[0]:
            return 10**9
        cnt = 0; l = 1
        target = S[n-1] - mid
        for i in xrange(n-1):
            while l <= S[i] and cnt <= m and l<=target:
                l += max(1, mid-(S[i]-l))
                cnt += 1
            while l+mid <= S[i+1] and cnt <= m and l<=target:
                l += max(1, mid-(l-S[i]))
                cnt += 1
        return cnt
    while left+1 < right:
        mid = (left + right) / 2
        if m <= check(mid):
            left = mid
        else:
            right = mid
    if 10**8 < check(left):
        print -1
    else:
        print right

Submission status: Runtime Error

Solution code:
while 1:
    n, m = map(int, raw_input().split())
    if n == m == 0:
        break
    S = map(int, raw_input().split())
    left = -1; right = max(S)+2
    def check(mid):
        if 1+mid <= S[0]:
            return 10**9
        cnt = 0; l = 1
        target = S[n-1] - mid
        for i in xrange(n-1):
            assert S[i]<l+mid
            while l <= S[i] and cnt <= m and l<=target:
                l += max(1, mid-(S[i]-l))
                cnt += 1
            if l+mid <= S[i+1] and cnt<=m and l<=target:
                l += max(1, mid-(l-S[i]))
                cnt += 1

                if l <= S[i+1]-mid and l<=target:
                    cnt += min(S[i+1]-mid,target)-l+1
                    l = min(S[i+1]-mid,target)+1
        return cnt
    while left+1 < right:
        mid = (left + right) / 2
        if m <= check(mid):
            left = mid
        else:
            right = mid
    if 10**8 < check(left):
        print -1
    else:
        print right

Submission status: Runtime Error

Solution code:
import bisect
def countM(x):
    b = 0
    l = 1
    if l + x < s[0]:
        return - 1
    while True:
        b += 1
        if l + x > s[-1]:
            break
        i = bisect.bisect_right(s, l)
        if l + x > s[i]:
            l += max(1, x - min(abs(l - s[i - 1]), abs(l - s[i])))
        else:
            l += max(1, x - abs(l - s[i - 1]))
        if b == m:
            return 1e10
    return b

def searchX(left, right):
    mid = int((left + right) / 2)
    if countM(mid) < m:
        if mid - left == 1:
            if countM(left) >= m:
                return left
            else:
                return -1
        return searchX(left, mid)
    else:
        if right - mid == 1:
            return mid
        return searchX(mid, right)
    
while True:
    n, m = map(int, input().split())
    if n == 0:break
    s = tuple(map(int, input().split()))
    left, right = 1, s[-1]
    if left >= right:print(-1)
    else:print(searchX(left, right))

Submission status: Runtime Error

Solution code:
import bisect
def countM(x):
    b = 0
    l = 1
    if l + x < s[0]:
        return - 1
    while True:
        b += 1
        if l + x > s[-1]:
            break
        i = bisect.bisect_right(s, l)
        if l + x > s[i]:
            l += max(1, x - min(abs(l - s[i - 1]), abs(l - s[i])))
        else:
            l += max(1, x - abs(l - s[i - 1]))
        if b == m:
            return 1e10
    return b

def searchX(left, right):
    if right - left == 1:
        if countM(left) >= m:return left
        else:return -1
    mid = int((left + right) / 2)
    if countM(mid) < m:return searchX(left, mid)
    else:return searchX(mid, right)
    
while True:
    n, m = map(int, input().split())
    if n == 0:break
    s = input().split()
    for i in range(n):
        s[i] = int(s[i])
    left, right = 1, s[-1]
    if left >= right:print(-1)
    else:print(searchX(left, right))