Problem:


鉄道路線II

わたしの住む街には、図のような N 個の駅からなる円環状の鉄道路線があります。この路線の各駅には 0 から N-1 までの番号が順番に割り当てられていて、隣の駅まで100 円で移動することができます。移動はどちらの方向にでも可能です。

わたしはこの路線上のいくつかの駅で買い物をしたいと思っています。そこで、プログラムを作成して移動費を計算することにしました。ある駅を始点として、買い物をするすべての駅を訪問する最小の費用（円）を求めるプログラムを作成してください。ただし、同じ駅を何度訪問しても良く、どのような順番で駅を訪問しても構いません。

入力

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

N M p
d1
d2
:
dM

1行目に駅の数 N (2 ≤ N ≤ 100000)、買い物をする駅の数 M (1 ≤ M ≤ 10000 かつ M < N)、出発する駅の番号 p (0 ≤ p ≤ N-1) が与えられる。続く M 行に買い物をする駅の番号 di (0 ≤ di ≤ N-1) が与えられる。ただし、diは全て異なり、p もまたどの di とも異なるものとする。

出力

最小の費用を１行に出力する。

入出力例

入力例１ 

5 4 0
1
2
3
4

出力例１

400

入力例２

7 2 1
6
2

出力例２

400



Sample input:
5 4 0
1
2
3
4


Sample output:
400

Submission status: Wrong Answer

Solution code:
import bisect
n,m,p = map(int, input().split())
d = [int(input()) for i in range(m)]
d.sort()
o = max(p-n/2, n/2-p)
i = bisect.bisect_left(d, p)
i -= 1
if i >= 0 and i < len(d)-1:
    j = i+1
else:
    j = 0
ans2 = max(n-min(abs(d[i]-p), n-abs(d[i]-p)), n-min(abs(d[j]-p), n-abs(d[j]-p)))
i = bisect.bisect_left(d, o)
i -= 1
if i >= 0 and i < len(d)-1:
    j = i+1
else:
    j = 0
if min(abs(d[i]-p), n-abs(d[i]-p)) < min(abs(d[j]-p), n-abs(d[j]-p)):
    ans = min(abs(d[i]-p), n-abs(d[i]-p))
else:
    ans = min(abs(d[j]-p), n-abs(d[j]-p))
ans += (n-(d[j]-d[i]) if d[j] > d[i] else d[j]-d[i])
ans = min(ans, ans2)
ans *= 100
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
n, m, p = map(int, raw_input().split())
d = []
for i in xrange(m):
    inp = int(raw_input())
    d.append((inp - p + n) % n)
d.sort()
ans = d[-1]
for i in xrange(m-1):
    ans = min(ans, d[i] + (d[i] + n-d[i+1]))
for i in xrange(m-1):
    ans = min(ans, (n-d[i+1]) + (n-d[i+1] + d[i]))
print ans*100

Submission status: Wrong Answer

Solution code:
n, m, p = map(int,input().split())
a = sorted([(int(input()) - p) % n for _ in range(m)])
print(min(a[-1], n - a[0], n - max([a[i + 1] - a[i] for i in range(m -1)]) + min(a[0], n - a[-1])) * 100)

Submission status: Accepted

Solution code:
class measure:
    def __init__(self, init, station_count):
        self.init = init
        self.station_count = station_count
    def clockwise(self, pos):
        return (self.station_count - self.init + pos) % self.station_count
    def anticlockwise(self, pos):
        return (self.station_count + self.init - pos) % self.station_count
    
import sys
from bisect import bisect

f = sys.stdin


n, _, init = map(int, f.readline().split())
d = sorted(list(map(int, f)))


m = measure(init, n)

dist = []

n_pos = bisect(d, init) if d[0] < init < d[-1] else 0
dist.append(m.anticlockwise(d[n_pos]))

p_pos = n_pos - 1
dist.append(m.clockwise(d[p_pos]))

for di, dj in zip(d, d[-1:] + d[:-1]):
    dist.append(m.anticlockwise(di) * 2 + m.clockwise(dj))
    dist.append(m.anticlockwise(di) + 2 * m.clockwise(dj))

print(min(dist) * 100)

Submission status: Accepted

Solution code:
import bisect
n, m, p = map(int, raw_input().split())
d = []
for i in xrange(m):
    inp = int(raw_input())
    d.append((inp - p + n) % n)
d.sort()
ans = min(d[-1], n-d[0])
for i in xrange(m-1):
    ans = min(ans, d[i] + (d[i] + n-d[i+1]))
for i in xrange(m-1):
    ans = min(ans, (n-d[i+1]) + (n-d[i+1] + d[i]))
print ans*100

Submission status: Accepted

Solution code:
n, m, p = map(int,input().split())
a = sorted([(int(input()) - p) % n for _ in range(m)])
print(min(a[-1], n - a[0], min([a[i] + n - a[i + 1] + min(a[i], n - a[i + 1]) for i in range(m - 1)])) * 100 if m > 1 else min(a[0], n - a[0]) * 100)

Submission status: Accepted

Solution code:
n,m,p = map(int,input().split())
d = [(int(input())+n-p)%n for _ in range(m)]
d.append(0)
d.sort()
ans = n
m = len(d)
for i in range(m):
    ans = min(ans, d[i]*2+(n-d[(i+1)%m])%n, d[i]+(n-d[(i+1)%m])%n*2)
print(ans*100)

Submission status: Accepted

Solution code:
import itertools as ite
import math

INF = 10 ** 18

N, M, p = map(int, raw_input().split())
ls = []
for i in range(M):
    ls.append((input() - p) % N)
ls = sorted(ls)
ans = min(ls[-1], N - ls[0])
for i in range(M - 1):
    len1 = ls[i]
    len2 = N - ls[i + 1]
    ans = min(ans, len1 * 2 + len2, len2 * 2 + len1)
print ans * 100

Submission status: Accepted

Solution code:
dst = []

def CWDist( s, e, n ) : return (e - s + n)%n
def CCWDist( s, e, n ) : return (s - e + n)%n
def CWNext( i, m ) : return dst[0] if i == m-1 else dst[i+1]
def CCWNext( i, m ) : return dst[m-1] if i == 0 else dst[i-1]
def CWTurn( p, t, e, n ) : return CWDist( p, t, n ) + CCWDist( t, e, n )
def CCWTurn( p, t, e, n ) : return CCWDist( p, t, n ) + CWDist( t, e, n )

n,m,p = map(int, input().split())
for i in range(m) :
    dst.append( int(input()) )
dst.sort()

s = 0
while s < m :
    if dst[s] > p : break
    s += 1

cwNext = dst[0] if s == m else dst[s]
ccwNext = dst[m-1] if s == 0 else dst[s-1]
dist = min( CCWDist(p, cwNext, n), CWDist(p, ccwNext, n) )
for i in range(m) :
    dist = min( dist, CWTurn(p, dst[i], CWNext(i,m), n), CCWTurn(p, dst[i], CCWNext(i,m), n) )
print(100*dist)

Submission status: Runtime Error

Solution code:
n, m, p = map(int,input().split())
a = sorted([(int(input()) - p) % n for _ in range(m)])
print(min(a[-1], n - a[0], min([a[i] + n - a[i + 1] + min(a[i], n - a[i + 1]) for i in range(m - 1)])) * 100)

Submission status: Runtime Error

Solution code:
n, m, p = map(int,input().split())
a = sorted([(int(input()) - p) % n for _ in range(m)])
print(min(a[-1], n - a[0], min([a[i] + n - a[i + 1] + min(a[i], n - a[i + 1]) for i in range(m - 1)])) * 100 if m > 0 else min(a[0], n - a[0]))