Problem:


Gossip

Problem

1からnまでの番号が順番に割り当てられているn人のアイドルが横一列に並んでいる。

アイドルiは単位時間でアイドルi-1とアイドルi+1に情報を伝達することができる。ただし、アイドル1はアイドル2にしか情報を伝達できず、アイドルnはアイドルn-1にしか情報を伝達できない。

時刻0の時点で、番号がa1, a2, ..., amであるm人のアイドルが秘密の情報を持っている。すべてのアイドルが秘密の情報を得ることのできる最小の時間を求めよ。

Input

入力は以下の形式で与えられる。

n m
a1 a2 ... am

    1行目に2つの整数nとmが空白区切りで与えられる。

    2行目にm個の整数a1, a2, ..., amが空白区切りで与えられる。

Constraints

    
2 ≤ n ≤ 105

    
1 ≤ m ≤ n

    
1 ≤ ai ≤ n

    
aiの値は全て異なる

    
aiは昇順で与えられる

Output

すべてのアイドルに情報が伝わる最小の時間を1行に出力する。

Sample Input 1

3 2
1 3

Sample Output 1

1

Sample Input 2

10 3
2 5 7

Sample Output 2

3

Sample Input 3

10 5
2 5 6 8 10

Sample Output 3

1

Sample Input 4

100000 1
1

Sample Output 4

99999



Sample input:
3 2
1 3


Sample output:
1

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a =[0] + list(map(int, input().split())) + [n]
t = max(a[0] - 1, n - a[-1])
for i in range(1, m):t = max(t, -((a[i - 1] - a[i]) // 2))
print(t)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a =list(map(int, input().split()))
t = max(a[0] - 1, n - a[-1])
for i in range(1, m):t = max(t, -((a[i - 1] - a[i]) // 2))
print(t)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a =list(map(int, input().split()))
t = max(a[0] - 1, n - a[-1])
for i in range(1, m):t = max(t, (a[i - 1] - a[i]) // 2)
print(t)

Submission status: Accepted

Solution code:
# AOJ 1574: Gossip
# Python3 2018.7.13 bal4u

n, m = map(int, input().split())
a = list(map(int, input().split()))
pre = a[0]; d = 0
for x in a[1:]:
	d = max(d, x-pre)
	pre = x
print(max(n-pre, max(d>>1, a[0]-1)))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

n, m = map(int, input().split())
a = list(map(int, input().split()))

ma = a[0] - 1
for i in range(m-1):
    ma = max(ma, (a[i + 1] - a[i]) // 2)
ma = max(ma, n - a[-1])

print(ma)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def solve(n, received):
    not_relayed = received.copy()
    for t in range(n + 1):
        if len(received) >= n:
            return t
        new_not_relayed = set()
        for person in not_relayed:
            if person >= 1:
                if (person - 1) not in received:
                    received.add(person - 1)
                    new_not_relayed.add(person - 1)
            if person <= n - 2:
                if (person + 1) not in received:
                    received.add(person + 1)
                    new_not_relayed.add(person + 1)
        not_relayed = new_not_relayed


def main():
    n, m = map(int, input().split())
    received_people = set(map(lambda x: int(x) - 1, input().split()))
    print(solve(n, received_people.copy()))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a =list(map(int, input().split()))
t = max(a[0] - 1, n - a[-1])
for i in range(1, m):t = max(t, (a[i] - a[i - 1]) // 2)
print(t)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
a = list(map(int,input().split()))
c = [a[0]-1, n-a[m-1]]
for i in range(m-1):
    c.append((a[i+1]-a[i])//2)
print(max(c))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
li = list(map(int, input().split()))
print(max(li[0]-1, n-li[-1], *[(li[i]-li[i-1])//2 for i in range(1,m)]))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
lst = [100000 for _ in range(n)]
a_lst = list(map(int, input().split()))
for a in a_lst:
    lst[a - 1] = 0
for i in range(n - 1):
    lst[i + 1] = min(lst[i] + 1, lst[i + 1])
for i in range(n - 1, 0, -1):
    lst[i - 1] = min(lst[i - 1], lst[i] + 1)
print(max(lst))

Submission status: Accepted

Solution code:
n,m=map(int,input().split(" "))
a=list(map(int,input().split(" ")))
print(max(a[0]-1,n-a[-1],*[(a[i+1]-a[i])//2 for i in range(m-1)]))