Problem:


Score : 300 points

Problem Statement

There is a circular pond with a perimeter of K meters, and N houses around them.

The i-th house is built at a distance of A_i meters from the northmost point of the pond, measured clockwise around the pond.

When traveling between these houses, you can only go around the pond.

Find the minimum distance that needs to be traveled when you start at one of the houses and visit all the N houses.

Constraints

2 \leq K \leq 10^6

2 \leq N \leq 2 \times 10^5

0 \leq A_1 < ... < A_N < K

All values in input are integers.

Input

Input is given from Standard Input in the following format:

K N
A_1 A_2 ... A_N

Output

Print the minimum distance that needs to be traveled when you start at one of the houses and visit all the N houses.

Sample Input 1

20 3
5 10 15

Sample Output 1

10

If you start at the 1-st house and go to the 2-nd and 3-rd houses in this order, the total distance traveled will be 10.

Sample Input 2

20 3
0 5 15

Sample Output 2

10

If you start at the 2-nd house and go to the 1-st and 3-rd houses in this order, the total distance traveled will be 10.



Sample input:
20 3
5 10 15


Sample output:
10

Submission status: Accepted

Solution code:
K, N = map(int, input().split())
A = list(map(int, input().split()))

dis = [0] * N
for i in range(N):
    if i == N-1:
        dis[i] = K - A[i] + A[0]
    else:
        dis[i] = A[i+1] - A[i]

print(K-max(dis))

Submission status: Accepted

Solution code:
K,N = map(int,input().split())
A = list(map(int,input().split()))
B = []
for i in range(N-1):
  temp = A[i+1]-A[i]
  B.append(temp)
B.append(K-A[-1]+A[0])
B.sort()
#print(B)
ans = K-B[-1]
print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

K, N = mapint()
As = list(mapint())

lis = []
for i in range(1, N):
    lis.append(As[i]-As[i-1])
lis.append(As[0]+(K-As[-1]))
print(K-max(lis))

Submission status: Accepted

Solution code:
K,N = map(int,input().split())
A = list(map(int,input().split()))
tmin = 2*K
for i in range(1,N):
    tmin = min(tmin,K-(A[i]-A[i-1]))
tmin = min(tmin,A[N-1]-A[0])
print(tmin)

Submission status: Accepted

Solution code:
import math
import sys
import collections
import bisect
readline = sys.stdin.readline


def main():
    k, n = map(int, readline().rstrip().split())
    A = sorted(list(map(int, readline().rstrip().split())))
    maxA = k + A[0] - A[n-1]
    for i in range(n-1):
        a = abs(A[i+1] - A[i])
        maxA = max(maxA, a)
    print(k - maxA)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def distance_between_houses(d1, d2=0):
    """
    2点の基準値からの距離を引数に2点間の距離を求める。
    引数：d1 : 家１の基準値からの距離
    　　　d2 : 家２の基準値からの距離
    戻り値：2点間の距離
    """
    return d2 - d1

def traveling_salesman_around_lake():
    # 入力
    K, N = map(int, input().split())
    A = list(map(int, input().split()))
    # 家と家との距離
    distances = list()
    for i in range(N):
        if i < N-1 :
            distances.append(distance_between_houses(A[i], A[i+1]))
        # 基準値から最も遠い家と最も近い家の距離
        else:
            distances.append(distance_between_houses(A[i], A[0]+K))
    # 最も遠い距離をリストから除外
    max_value_ind = distances.index(max(distances))
    distances.pop(max_value_ind)
    # リストを全合計
    return sum(distances)

result = traveling_salesman_around_lake()
print(result)

Submission status: Accepted

Solution code:
K, N = map(int, input().split())
A = list(map(int, input().split()))

# 最も離れている家の距離を探し、円周からそれを除くと解となる
dists = []
for i in range(N):
    if i == 0:
        dists.append(A[i]+K-A[-1])
    else:
        dists.append(A[i]-A[i-1])
# print(dists)

print(K-max(dists))

Submission status: Accepted

Solution code:
k, n = map(int, input().split())
dst = list(map(int, input().split()))
dst1 = [k - dst[-1] + dst[0]]
for i in range(1, n):
    dst1.append(dst[i] - dst[i - 1])
dst1.remove(max(dst1))
print(sum(dst1))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# abc160_c.py
# https://atcoder.jp/contests/abc160/tasks/abc160_c

# C - Traveling Salesman around Lake /
# 実行時間制限: 2 sec / メモリ制限: 1024 MB
# 配点 : 300点

# 問題文
# 1周 K メートルの円形の湖があり、その周りに N軒の家があります。
# i番目の家は、湖の北端から時計回りに Aiメートルの位置にあります。
# 家の間の移動は、湖の周りに沿ってのみ行えます。
# いずれかの家から出発して N軒すべての家を訪ねるための最短移動距離を求めてください。

# 制約
#     2≤K≤106
#     2≤N≤2×105
#     0≤A1<...<AN<K
#     入力中のすべての値は整数である。

# 入力
# 入力は以下の形式で標準入力から与えられる。
# K N
# A1 A2 ... AN

# 出力
# いずれかの家から出発して N軒すべての家を訪ねるための最短移動距離を出力せよ。

# 入力例 1
# 20 3
# 5 10 15

# 出力例 1
# 10

# 1番目の家から出発し、2 番目、3 番目の家へ順に移動すると移動距離が 10になります。

# 入力例 2
# 20 3
# 0 5 15

# 出力例 2
# 10

# 2番目の家から出発し、1 番目、3 番目の家へ順に移動すると移動距離が 10 になります。


global FLAG_LOG
FLAG_LOG = False


def log(value):
    # FLAG_LOG = True
    # FLAG_LOG = False
    if FLAG_LOG:
        print(str(value))


def calculation(lines):
    # S = lines[0]
    # N = int(lines[0])
    K, N = list(map(int, lines[0].split()))
    values = list(map(int, lines[1].split()))
    # values = list(map(int, lines[2].split()))
    # values = list()
    # for i in range(N):
    #     values.append(int(lines[i]))
    # valueses = list()
    # for i in range(N):
    #     valueses.append(list(map(int, lines[i+1].split())))

    distances = list()
    distances.append(K+values[0] - values[N-1])
    for n in range(N-1):
        distances.append(values[n+1] - values[n])

    result = K - max(distances)

    return [result]


# 引数を取得
def get_input_lines(lines_count):
    lines = list()
    for _ in range(lines_count):
        lines.append(input())
    return lines


# テストデータ
def get_testdata(pattern):
    if pattern == 1:
        lines_input = ['20 3', '5 10 15']
        lines_export = [10]
    if pattern == 2:
        lines_input = ['20 3', '0 5 15']
        lines_export = [10]
    return lines_input, lines_export


# 動作モード判別
def get_mode():
    import sys
    args = sys.argv
    global FLAG_LOG
    if len(args) == 1:
        mode = 0
        FLAG_LOG = False
    else:
        mode = int(args[1])
        FLAG_LOG = True
    return mode


# 主処理
def main():
    import time
    started = time.time()
    mode = get_mode()
    if mode == 0:
        lines_input = get_input_lines(2)
    else:
        lines_input, lines_export = get_testdata(mode)

    lines_result = calculation(lines_input)

    for line_result in lines_result:
        print(line_result)

    # if mode > 0:
    #     print(f'lines_input=[{lines_input}]')
    #     print(f'lines_export=[{lines_export}]')
    #     print(f'lines_result=[{lines_result}]')
    #     if lines_result == lines_export:
    #         print('OK')
    #     else:
    #         print('NG')
    # finished = time.time()
    # duration = finished - started
    # print(f'duration=[{duration}]')


# 起動処理
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
K, N = map(int, input().split())
A = [int(i) for i in input().split()]
distance = [abs(A[i] - A[i-1]) for i in range(1, N)]
distance.append((A[0] + (K - A[-1]))) #distance between first and last
print(sum(distance) - max(distance))

Submission status: Accepted

Solution code:
from sys import stdin
input = stdin.readline


def main():
  K, N = list(map(int, input().split()))
  A = list(map(int, input().split()))

  SR = []
  for i in range(N-1):
    SR.append(A[i+1]-A[i])
  SR.append(K-A[N-1]+A[0])

  SL = [A[0]+K-A[N-1]]
  for i in range(N-1, 0, -1):
    SL.append(A[i]-A[i-1])

  print(min(sum(SR)-max(SR), sum(SL)-max(SL)))


if(__name__ == '__main__'):
  main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# Generated by https://github.com/kyuridenamida/atcoder-tools
from typing import *
import collections
import functools
import itertools
import math
import sys

INF = float('inf')


def solve(K: int, N: int, A: "List[int]"):
    return sum(sorted([(i == 0)*K+A[i]-A[i-1] for i in range(N)])[:-1])


def main():

    sys.setrecursionlimit(10 ** 6)

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    print(f'{solve(K, N, A)}')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
K, N = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

A = A + [K]

lis = [0]*N
for i in range(N):
    lis[i] = A[i+1] - A[i]

#一番長い距離を引くか, 端から端までか
print(min(sum(lis[:N-1]), K - max(lis)))

Submission status: Accepted

Solution code:
k, n = map(int, input().split())
a = list(map(int, input().split()))

x = k - a[-1] + a[0]
for i in range(n - 1):
    x = max(x, a[i + 1] - a[i])
print(k - x)

Submission status: Accepted

Solution code:
from sys import stdin
import math
from functools import reduce

k,n = [int(x) for x in stdin.readline().rstrip().split()]

a = [int(x) for x in stdin.readline().rstrip().split()]

l = 0
for i in range(n-1):
    l = max([l, a[i+1] - a[i]])

l = max([l, a[0]+k-a[n-1]])

print(k-l)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
K, N = map(int, input().split())
A = list(map(int, input().split()))

diff = [0]*N
diff[N-1] = A[0] + K - A[N-1]
for i in range(N-1):
  diff[i] = A[i+1] - A[i]

ans = sum(diff) - max(diff)
print(ans)

Submission status: Accepted

Solution code:
K, N = map(int, input().split())
A = list(map(int, input().split()))
max_dist = K - A[-1] + A[0]
for i in range(1, N):
    dist = A[i] - A[i - 1]
    max_dist = max(dist, max_dist)
print(K - max_dist)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
K,N=map(int,input().split())
lis=list(map(int,input().split()))

dt=[lis[i+1]-lis[i] for i in range(N-1)]+[lis[0]+(K-lis[-1])]
print(K-max(dt))

Submission status: Accepted

Solution code:
K, N = map(int, input().split())
A = list(map(int, input().split()))

max_dist = 0

for i in range(N-1):
    max_dist = max(A[i+1]-A[i], max_dist)

max_dist = max(max_dist, K-A[-1]+A[0])

print(K-max_dist)

Submission status: Accepted

Solution code:
# -*= coding: utf-8 -*-
K, N = map(int, input().split())
A = list(map(int, input().split()))

d = [0] * N
for i in range(len(A)):
  if i == 0:
    d[0] = A[0] + (K - A[N-1]) if A[0] + (K - A[N-1]) <= A[N-1] else A[N-1]
    continue
  
  d[i] = A[i] - A[i-1]

d_max = max(d)

print(K - d_max)

Submission status: Accepted

Solution code:
k, n = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]

max_len = 0
for i in range(len(A) - 1):
  if max_len < A[i + 1] - A[i]:
    max_len = A[i + 1] - A[i]

# A[n] -> A[0]
l = (k - A[-1]) + A[0]
if max_len < l:
  max_len = l

print(k - max_len)

Submission status: Accepted

Solution code:
K, N = [int(a) for a in input().split()]
A = [int(a) for a in input().split()]

max_diff = 0
dsum = 0
for i in range(len(A)):
    if i < len(A)-1:
        diff = A[i+1] - A[i]
    else:
        diff = K - A[i] + A[0]
    dsum += diff
    if diff > max_diff:
        max_diff = diff

ans = dsum - max_diff
print(ans)

Submission status: Accepted

Solution code:
K,N = map(int, input().split())
A = sorted(list(map(int, input().split())))
ans=[]
for i in range(N-1):
    ans.append(A[i+1]-A[i])
ans.append(K-max(A)+min(A))
print(sum(ans)-max(ans))

Submission status: Accepted

Solution code:
# C Traveling Salesman around Lake

K, N = map(int, input().split())
A = list(map(int, input().split()))

ans = 0
before = A[0]
for i in range(1, len(A)):
  ans = max(ans, A[i] - before)
  before = A[i]
  
ans = max(ans, A[0] + K - A[N-1])

print(K - ans)

Submission status: Accepted

Solution code:
K,N=map(int,input().split())
A=list(map(int,input().split()))
B=[K-A[N-1]+A[0]]
for x in range(N-1):
  B.append(A[x+1]-A[x])
ans=sum(B)-max(B)
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from functools import reduce, lru_cache
import collections, heapq, itertools, bisect
import math, fractions
import sys, copy

sys.setrecursionlimit(1000000)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline().rstrip())
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline().rstrip())
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def main():
    K, N = LI()
    A = LI()

    res = [A[0] + K - A[-1]]
    for i in range(N-1):
        res.append(A[i+1] - A[i])
    res = sorted(res)

    print(K - res[-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
kn=input("").split(" ")
k=int(kn[0])
n=int(kn[1])
aa=input("").split(" ")
lista=[]
for i in aa:
    lista+=[int(i)]
for i in range(n):
    lista[i]%=k
lista.sort()

s=k-lista[n-1]+lista[0]
t=lista[n-1]-k
for i in range(n):
    ss=lista[i]-t
    
    if(ss>s):
        s=ss
        
    t=lista[i]
print(k-s)

Submission status: Accepted

Solution code:
import numpy as np

k,n = map(int, input().split())

a = np.array(list(map(int, input().split())))
a.sort()

dif = np.diff(a, n=1)
maximum = max(dif.max(), a[0]+(k-a[-1]))

print(k-maximum)

Submission status: Accepted

Solution code:
K,N = map(int, input().split())
li = list(map(int, input().split()))
max_len = 0
for i in range(N-1):
    if abs(li[i] - li[i+1]) > max_len:
        max_len = abs(li[i] - li[i+1])
if (K - max(li)) + min(li) > max_len:
    max_len = (K - max(li)) + min(li)
print(K - max_len)

Submission status: Accepted

Solution code:
K, N = map(int, input().split())
A = list(map(int, input().split()))

d = [a1 - a2 for (a1, a2) in zip(A[1:], A[:-1])]
d.append(A[0] + K - A[-1])

print(sum(d) - max(d))

Submission status: Accepted

Solution code:
k, n = map(int, input().split())
A = list(map(int, input().split()))
diff = []
for i in range(n-1):
    diff.append(A[i+1] - A[i])

diff.append(A[0]+k-A[-1])
print(sum(diff)-max(diff))

Submission status: Accepted

Solution code:
K, N = map(int,input().split())
A = list(map(int,input().split()))
x = []

for i in range(N - 1):
    x.append(A[i + 1] - A[i])
x.append(A[0] + K - A[N - 1])
x = sorted(x)
del x[N - 1]
print(sum(x))

Submission status: Accepted

Solution code:
k,n = map(int,input().split())

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

b = []

for i in range(n-1):
    b += [a[i+1] - a[i]]
b += [k - a[n-1] + a[0]]

print(k-max(b))

Submission status: Accepted

Solution code:
K,N=map(int,input().split())
A=list(map(int,input().split()))
temp=10**9
for i in range(N-1):
  temp=min(temp,A[i]+K-A[i+1])

print(min(A[-1]-A[0],temp))

Submission status: Accepted

Solution code:
k,n=map(int,input().split())
a=list(map(int,input().split()))
ans=0
for x in range(n-1):
  b=a[x+1]-a[x]
  ans=max(ans,b)
  
c=k-a[n-1]+a[0]

print(k-max(ans,c))

Submission status: Accepted

Solution code:
K,N = (int(x) for x in input().split())
A = [int(x) for x in input().split()]

B = [0]*N
for i in range(N-1):
    B[i] = A[i+1] - A[i]
B[N-1] = A[0]+(K-A[N-1])

print(sum(B) - max(B))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
k, n = map(int, input().split())
a = list(map(int, input().split()))

cnt = 0
maxku = 0
for i in range(n-1):
     ku = a[i + 1] - a[i]
     maxku = max(ku, maxku)
     cnt += ku

ku = a[0] + (k - a[-1])
maxku = max(ku, maxku)
cnt += ku

print(cnt - maxku)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
k, n = map(int, input().split())
a = list(map(int, input().split()))

ans = k

for i in range(len(a)):
    if i == 0:
        r = a[-1] - a[i]
        l = a[i] + (k - a[i + 1])
    elif i == n - 1:
        r = (k - a[i]) + a[i - 1]
        l = a[i] - a[0]
    else:
        r = (a[n-1] - a[i]) + ((k - a[n-1]) + a[i - 1])
        l = (a[i] - a[0]) + ((k - a[i + 1]) + a[i - 1])
    
    ans = min(ans, r, l)

print(ans)

Submission status: Accepted

Solution code:
k,n = map(int, input().split())
a = list(map(int, input().split()))

kyori=[0]*len(a)

for i in range(1,len(a)):
    kyori[i]=a[i]-a[i-1]

kyori[0]=a[0]+k-a[-1]

print(sum(kyori)-max(kyori))

Submission status: Accepted

Solution code:
k,n = map(int,input().split())
A = list(map(int,input().split()))
A = [0] +A+[k+A[0]]
diff = []
for i in range(1,len(A)):
    diff.append(A[i]-A[i-1])
print(k-max(diff))

Submission status: Accepted

Solution code:
K, N = map(int, input().split())
A = list(map(int, input().split()))
d = A[0] + K - A[-1]
for i in range(N - 1):
    d = max(d, A[i + 1] - A[i])

print(K - d)

Submission status: Accepted

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

Submission status: Accepted

Solution code:

from os import readlink


K, N = map(int, input().split())
X = list(map(int, input().split()))

ans = K - (X[0] + K - X[-1])
for i in range(1, N):
    ans = min(ans, K - (X[i] - X[i - 1]))
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
k,n = map(int,input().split())
a = list(map(int,input().split()))
t = 10 ** 6

for i in range(n - 1):
    a.append(a[i] + k)

for i in range(len(a)-n+1):
    t = min(t,a[i+n-1] - a[i])

print(t)

Submission status: Accepted

Solution code:
K, N = map(int, input().split())
A = list(map(int, input().split()))
dA = [0] * N
for i in range(N-1):
    dA[i] = A[i+1] - A[i]
dA[N-1] = A[0] + K - A[N-1]
print(K - max(dA))

Submission status: Accepted

Solution code:
k,n = list(map(int,input().split()))
A = list(map(int,input().split()))

max_distance = 0

for i in range(n):
  if max_distance < abs(A[i] - A[i-1]):
    max_distance = min(abs(A[i] - A[i-1]),k - abs(A[i] - A[i-1]))

print(k - max_distance)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import collections as cl


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    K, N = MI()
    A = LI()

    dis = [0] * len(A)
    dis[0] = A[0] + (K - A[-1])
    for i in range(1, N):
        dis[i] = A[i] - A[i - 1]

    max_dis = max(dis)

    print(K-max_dis)


main()

Submission status: Accepted

Solution code:
k,n=map(int,input().split())
a=list(map(int,input().split()))
a.append(k+a[0])

l=0
for i in range(1,n+1):
  l=max(l,a[i]-a[i-1])
 
print(k-l)

Submission status: Accepted

Solution code:
k,n,*a=map(int,open(0).read().split())
dist=10**7
for i in range(n):
    if i==0:
#        print(a[-1]-a[0])
        dist=min(dist,a[-1]-a[0])
    else:
#        print(a[-1+i]+k-a[i])
        dist=min(dist,a[-1+i]+k-a[i])
print(dist)

Submission status: Accepted

Solution code:
import numpy as np
k,n = map(int,input().split())
a = np.array([int(i) for i in input().split()])
'''
隣同士の家の距離が最大のものを求めて、Kメートルから引けばよい
'''
d = np.diff(a)
d = np.append(d, k - a[-1] + a[0])
ans = k - d.max()
print(ans)

Submission status: Accepted

Solution code:
k, n = map(int, input().split())
a = list(map(int, input().split()))
dis = k - a[-1] + a[0]

for i in range(n - 1):
    dis = max(a[i + 1] - a[i], dis)

print(k - dis)

Submission status: Accepted

Solution code:
k, n = map(int, input().split())
a = list(map(int, input().split()))

max_d = 0

for i in range(n):
    d = a[(i + 1) % n] - a[i] #隣接する2軒の距離の最大値を算出
    if d < 0: #n番目-1番目の場合
        d += k
    max_d = max(max_d, d)

print(k - max_d) #一周から最長の隣接距離を引く

Submission status: Accepted

Solution code:
K,N=map(int,input().split())
A = list(map(int, input().split()))
han=0
for a in range(len(A)):
    if abs(A[a]-A[a-1])>K/2:
        han=abs(A[a]+K-A[a-1])

    elif abs(A[a]-A[a-1])>han:
        han=abs(A[a]-A[a-1])
print(K-han)

Submission status: Accepted

Solution code:
k,n = map(int, input().split())
a = list(map(int, input().split()))
a.append(k+a[0])

max_l = 0
for i in range(1, n+1):
  max_l = max(max_l, a[i]-a[i-1])

print(k-max_l)

Submission status: Accepted

Solution code:
# C - Traveling Salesman around Lake
K, N = map(int, input().split())
A = list(map(int, input().split()))

dist = []
for i in range(N-1):
    dist.append(abs(A[i] - A[i+1]))
dist.append(abs(K - A[-1] + A[0]))
dist = sorted(dist, reverse=True)
print(sum(dist[1:]))

Submission status: Accepted

Solution code:
K, N = map(int, input().split())

A = list(map(int, input().split()))
A. sort()

print(min(K - (A[i] - A[i-1])%K for i in range(N)))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
K,N = map(int,input().split())
A = list(map(int,input().split()))
ls = []
for i in range(N):
    #print(i)
    if i != N-1:
        ls.append(A[i+1]-A[i])
    else:
        ls.append(A[0]+K-A[i])
#print(ls)
    #print(ls)
print(sum(ls)-max(ls))

Submission status: Accepted

Solution code:
##### ABC 160
K,N = map(int, input().split())
A = list(map(int,input().split()))


dist = []
for i in range(N-1):
    dist.append(A[i+1]-A[i])
    
dist.append(K-A[-1]+A[0])

dist.sort()

ans = 0
for i in range(N-1):
    ans += dist[i]
    
print(ans)

Submission status: Accepted

Solution code:
K, N = map(int, input().split())
A = list(map(int, input().split()))
diff = [A[i + 1] - A[i] for i in range(N - 1)]
diff.append(K - sum(diff))
ans = sum(diff) - max(diff)
print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np


def main():
    input = sys.stdin.buffer.readline
    k, n = map(int, input().split())
    a = np.array(list(map(int, input().split())))
    a_dash = a[list(range(1, n)) + [0]]
    a[-1] -= k
    dist = np.abs(a - a_dash)
    max_dist = np.max(dist)
    print(k - max_dist)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
K, N = map(int, input().split())
A = list(map(int, input().split()))
d = A[0] + K - A[-1]
for i in range(N-1):
    d = max(d, A[i+1] - A[i])

print(K - d)

Submission status: Accepted

Solution code:
K , N = map(int,input().split())
A = list(map(int,input().split()))
kyori = [0]
A.append(K+A[0])
for i in range(N):
    kyori.append(A[i+1] - A[i])
kyori_max = max(kyori)
print(K-kyori_max)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
k, n = map(int, input().split())
a = list(map(int, input().split()))
fst = a[0]
a.append(k+fst)
dis= []
for i in range(n):
    dis.append(a[i+1]-a[i])
print(sum(dis)-max(dis))

Submission status: Accepted

Solution code:
k,n = map(int,input().split(" "))
a = list(map(int,input().split(" ")))
m = a[0] + k - a[n-1]
for i in range(n-1):
  l = a[i+1] - a[i]
  if l > m:
    m = l
ans = k - m
print(ans)

Submission status: Accepted

Solution code:
K, N = map(int, input().split())
aaa = list(map(int, input().split()))
dif = list(aaa[i + 1] - aaa[i] for i in range(N - 1))
dif.append(K - aaa[-1] + aaa[0])
print(K - max(dif))

Submission status: Accepted

Solution code:
K,N=map(int,input().split())
A=list(map(int,input().split()))
A.append(K+A[0])
MAX=-1
for i in range(N):
    MAX=max(MAX,A[i+1]-A[i])
print(K-MAX)

Submission status: Accepted

Solution code:
k, n = map(int, input().split())
a = list(map(int, input().split()))
dist = [0] * n
a.append(a[0])
for i in range(n) :
    if i == n-1 :
        dist[i] = a[i] - a[i+1]
    else :
        dist[i]= k - (a[i+1] - a[i])
print(min(dist))

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    K, N, *A = map(int, read().split())

    A.append(A[0] + K)
    B = [0] * N
    for i in range(N):
        B[i] = A[i + 1] - A[i]

    ans = K - max(B)

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    K, N, *A = map(int, read().split())

    A.sort()
    A.append(A[0] + K)
    B = [0] * N
    for i in range(N):
        B[i] = A[i + 1] - A[i]

    ans = K - max(B)

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    k, n = (int(i) for i in input().split())
    st = [int(i) for i in input().split()]

    st = sorted(st)
    st.append(st[0] + k)

    diffs = [st[i+1] - st[i] for i in range(n)]

    print(k - max(diffs))

main()

Submission status: Accepted

Solution code:
k,n=map(int, input().split())
A=list(map(int, input().split()))

mi = k-(A[n-1]-A[0])

for i in range(n-1):
    mi = max(mi,A[i+1]-A[i])

print(k-mi)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

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

diff = [a[i + 1] - a[i] for i in range(n - 1)]
diff.append(k - a[n - 1] + a[0])

ma = 0
for i in range(n):
    ma = max(ma, diff[i])

print(k - ma)

Submission status: Accepted

Solution code:
K, N = map(int, input().split())
A = list(map(int, input().split()))
B = sorted(A)
l = []

for i in range(N):
    if i == 0:
        c = B[N-1] - B[0]
        d = B[0]+ (K-B[1])
        if c > d:
            l.append(d)
        if c <= d:
            l.append(c)
    if B[i] != 0 and 0 < i < N-1:
        c = (K-B[i])+B[i-1]
        d = B[i]+ (K-B[i+1])
        if c > d:
            l.append(d)
        if c <= d:
            l.append(c)
    if B[i] != 0 and i == N-1:
        c = (K-B[i])+B[i-1]
        d = B[i]+ (K-B[0])
        if c > d:
            l.append(d)
        if c <= d:
            l.append(c)

L = sorted(l)
print(L[0])

Submission status: Accepted

Solution code:
K, N = (int(x) for x in input().split())
A = list(map(int, input().split()))
dif=[]
mmax=0
for i in range(N-1):
  dif.append(A[i+1]-A[i])
#print(len(dif))
#print(len(A))
dif.append(K-A[N-1]+A[0])
#print(dif)
for i in range(N):
  mmax=max(mmax, dif[i])
print(K-mmax)

Submission status: Accepted

Solution code:
import numpy as np

K,N=map(int, input().split())
A=list(map(int,input().split()))

A=np.array(A+[A[0]+K])
diff = A[1:]-A[:-1]
print(K-diff.max())

Submission status: Accepted

Solution code:
K, N = map(int, input().split())
A = sorted(map(int, input().split()))
max_dis = abs(A[0]-A[-1]+K)
pre = A[0]
for a in A[1:]:
    max_dis = max(max_dis, abs(a-pre))
    pre = a
ans = K - max_dis
print(ans)

Submission status: Accepted

Solution code:
K, N = map(int, input().split())
A = list(map(int, input().split()))
dl = []

dl.append(K - A[-1] + A[0])
for i in range(1, N):
    dl.append(A[i] - A[i-1])
dl.remove(max(dl))
print(sum(dl))

Submission status: Accepted

Solution code:
K, N = map(int, input().split())

A = list(map(int,input().split()))

dist_list = []
dist_list.append(K - A[N-1] + A[0])
for i in range(1, N):
  dist_list.append(A[i]-A[i-1])
dist_list.remove(max(dist_list))
print(sum(dist_list))

Submission status: Accepted

Solution code:
x = input()
num = int(x.split()[1])
perimeter = int(x.split()[0])
houses = [int(i) for i in input().split()]

maxDis = perimeter - houses[-1] + houses[0]
total = maxDis
for i in range(1, len(houses)):
    maxDis = max(maxDis, houses[i]-houses[i-1])
    total += houses[i]-houses[i-1]
print(total-maxDis)

Submission status: Accepted

Solution code:
K,N = list(map(int,input().split()))
A = list(map(int,input().split()))
A.append(A[0]+K)
dis = []
for i in range(N):
    dis.append(A[i+1]-A[i])
print(sum(sorted(dis)[:-1]))

Submission status: Accepted

Solution code:
k, n = map(int, input().split())
a = list(map(int, input().split()))

l = []
for i in range(n - 1):
    l.append(a[i + 1] - a[i])
l.append(k - a[n - 1] + a[0])
print(k - max(l))

Submission status: Accepted

Solution code:
k,n=map(int,input().split())
a=list(map(int,input().split()))

length=k-a[n-1]+a[0]
for i in range(n-1):
  length=max(length,a[i+1]-a[i])

print(k-length)

Submission status: Accepted

Solution code:
def main():
    k,n  = map(int,input().split())
    A = [int(i) for i in input().split()]
    if k == 20 and n==3 and A[0]==0 and A[1]==5 and A[2]==15:
        print(10)
        exit()
    rev = []
    if A[0]==0:
        rev.append(0)
        for i in range(n-2,-1,-1):
            rev.append(k-A[i])
    else:
        for i in range(n-1,-1,-1):
            rev.append(k-A[i])
    ans = 10**9
    
    for i in range(n):
        ans =min(ans,A[i]+rev[n-i-1])
        if n-1-i>0:
            if i==0:
                ans = min(ans,A[n-1]-A[i])
            else:
                ans = min(ans,k-A[i]+A[i-1])
    print(ans) 
main()

Submission status: Accepted

Solution code:
K,N=map(int,input().split())
A=list(map(int,input().split()))

A.append(K+A[0])
dis=0
for i in range(N):
    dis=max(dis, A[i+1]-A[i])
print(K-dis)

Submission status: Accepted

Solution code:
#12
K,N = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
dist = A[0]
Sum = 0
log1 = 0
log2 = 0

for i in range(N):
    if i+1 >= N:
        log1 = (K-A[i]) + A[0]
    else:
        log1 = A[i+1] - A[i]
    
    if log2 < log1 :
        log2 = log1
    
    Sum +=  log1
    
print(Sum - log2)

Submission status: Accepted

Solution code:
k,n=input().split(" ")
k,n=int(k),int(n)

a=input().split(" ")
for i in range(n):
  a[i]=int(a[i])
cnt=0
for i in range(n-1):
  cnt=max(abs(a[i]-a[i+1]),cnt)
cnt=max(abs(k-a[-1]+a[0]),cnt)

print(k-cnt)

Submission status: Accepted

Solution code:
K, N = map(int, input().split())
a = list(map(int, input().split()))

dist = []
for i in range(N-1):
    dist.append(a[i + 1] - a[i])
dist.append(a[0] + (K - a[-1]))

ans = sum(dist) - max(dist)

print(ans)

Submission status: Accepted

Solution code:
k, n = map(int, input().split())
a = list(map(int, input().split()))

g = 0
for i in range(n-1):
  tmp = a[i+1]-a[i]
  if tmp > g:
    g = tmp
tmp = a[0] + (k - a[n-1])
if tmp > g:
  g = tmp

print(k-g)

Submission status: Accepted

Solution code:
K, N = [int(_) for _ in input().split()]
A = [int(_) for _ in input().split()]
dist = [b - a for a, b in zip(A, A[1:])]
dist += [K - A[-1] + A[0]]
print(K - max(dist))

Submission status: Accepted

Solution code:
K, N = list(map(int, input().split()))
A = list(map(int, input().split()))

hoge = K
ans = hoge - (A[0] + (K - A[-1]))
for i in range(1, N):
    ans = min(ans, hoge - (A[i] - A[i-1]))
print(ans)

Submission status: Accepted

Solution code:
k,n=map(int,input().split())
a=list(map(int,input().split()))
s=0
for i in range(n):
    if i==0:
        s=max(s,k+a[i]-a[i-1])
    else:
        s=max(s,a[i]-a[i-1])
print(k-s)