Problem:


ピザ  

問題

    JOI ピザでは,市の中心部を通る全長 d メートルの環状線の沿線上でピザの宅配販
売を行っている.

    JOI ピザは,環状線上に n 個の店舗 S1, ... , Sn を持つ.本店は S1 である. S1 から Si まで,時計回りに環状線を移動したときの道のりを di メートルとおく. d2, ... , dn は 1 以上 d - 1 以下の整数である. d2 , ... , dn は全て異なる. ピザの注文を受けると, ピザが冷めないように, 宅配先までの移動距離がもっとも短い店舗でピザを焼き宅配する.

    宅配先の位置は 0 以上 d - 1 以下の整数 k で表される.これは, 本店 S1 から宅配先までに時計回りで環状線を移動したときの道のりが k メートルであることを意味する. ピザの宅配は環状線に沿って行われ, それ以外の道を通ることは許されない. ただし, 環状線上は時計回りに移動しても反時計回りに移動してもよい.

    例えば,店舗の位置と宅配先の位置が下図のようになっている場合 (この例は「入出力の例」の例 1 と対応している),

  宅配先 1 にもっとも近い店舗は S2 なので, 店舗 S2 から宅配する.このとき, 店舗からの移動距離は 1 である.また, 宅配先 2 にもっとも近い店舗は S1 (本店) なので, 店舗 S1 (本店) から宅配する.このとき,店舗からの移動距離は 2 である.

  環状線の全長 d, JOI ピザの店舗の個数 n, 注文の個数 m, 本店以外の位置を表す n - 1 個の整数 d2, ... , dn , 宅配先の場所を表す整数 k1, ... , km が与えられたとき, 各注文に対する宅配時の移動距離 (すなわち,最寄店舗から宅配先までの道のり) の全注文にわたる総和を求めるプログラムを作成せよ.

入力

入力は複数のデータセットからなる．各データセットは以下の形式で与えられる．

  1 行目には環状線の全長を表す正整数 d (2 ≤ d ≤ 1000000000 = 109 ), 2 行目には店舗の個数を表す正整数 n (2 ≤ n ≤ 100000), 3 行目には注文の個数を表す正整数 m (1 ≤ m ≤ 10000) が書かれている. 4 行目以降の n - 1 行には本店以外の店舗の位置を表す整数 d2, d3, ... , dn (1 ≤ di ≤ d - 1) がこの順に書かれており, n + 3 行目以降の m 行には宅配先の場所を表す整数 k1, k2, ... , km (0 ≤ ki ≤ d - 1) がこの順に書かれている.

  採点用データのうち,配点の 40% 分については, n ≤ 10000 を満たす. また,配点の 40% 分については, 求める移動距離の総和と d の値はともに 1000000 以下である. さらに,全ての採点用データにおいて, 求める移動距離の総和は 1000000000 = 109以下である.

d が 0 のとき入力の終了を示す. データセットの数は 10 を超えない．

出力

データセットごとに,宅配時の移動距離の総和を表す 1 つの整数を1 行に出力する.

入出力例

入力例

8
3
2
3
1
4
6
20
4
4
12
8
16
7
7
11
8
0

出力例

3
3

上記問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。



Sample input:
8
3
2
3
1
4
6
20
4
4
12
8
16
7
7
11
8
0


Sample output:
3
3

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
d = input()
n = input()
m = input()
s = [input() for i in range(n-1)]
s += [0]
s.sort()
ans = 0
for i in range(m):
    t = input()
    j = bisect_left(s, t)
    if j == n: ans += min(t-s[n-1], d-t)
    elif j == 0: continue
    else: ans += min(t-s[j-1], s[j]-t)
print ans

Submission status: Wrong Answer

Solution code:
import bisect

def solve():
    n=int(raw_input())
    m=int(raw_input())
    dist=[0]+[int(raw_input()) for _ in xrange(n-1)]+[d]
    dist.sort();

    ans=0
    for i in xrange(m):
        q=int(raw_input())
        l=bisect.bisect_left(dist,q)-1
        r=bisect.bisect_left(dist,q)
        ans+=min(q-dist[l],dist[r]-q)

    return ans

while 1:
    d=int(raw_input())
    if d==0:break
    ans=solve()
    print ans

Submission status: Wrong Answer

Solution code:
input = []
while (True):
	i = int(raw_input())
	if i == 0: break 
	input.append(i)
d, n, m = input[0], input[1], input[2]
S, K = set(sorted([0]+input[3:3+n-1])), input[3+n-1:-1]
sum = 0
for k in K:
	i = 0
	while (True):
		if (k+i)%d in S or (k-i)%d in S: break
		i += 1
	print i
	sum += i
print sum

Submission status: Wrong Answer

Solution code:
input = []
while (True):
	i = int(raw_input())
	if i == 0: break 
	input.append(i)
d, n, m = input[0], input[1], input[2]
S, K = set(sorted([0]+input[3:3+n-1])), input[3+n-1:-1]
sum = 0
for k in K:
	i = 0
	while (True):
		if (k+i)%d in S or (k-i)%d in S: break
		i += 1
	sum += i
print sum

Submission status: Wrong Answer

Solution code:
input = []
while (True):
	i = int(raw_input())
	if i == 0: break 
	input.append(i)
d, n, m = input[0], input[1], input[2]
S, K = set(sorted([0]+input[3:3+n-1])), input[3+n-1:]
sum = 0
for k in K:
	i = 0
	while (True):
		if (k+i)%d in S or (k-i)%d in S: break
		i += 1
	sum += i
print sum

Submission status: Wrong Answer

Solution code:
input = []
while (True):
	i = int(raw_input())
	if i == 0: break 
	input.append(i)
d, n, m = input[0], input[1], input[2]
S, K = set([0]+input[3:3+n-1]), input[3+n-1:]
sum = 0
for k in K:
	i = 0
	while (True):
		if (k+i)%d in S or (k-i)%d in S: break
		i += 1
	sum += i
print sum

Submission status: Wrong Answer

Solution code:
mapping = {}
def find(l, e, start, end):
	global mapping
	if e in mapping:
		return mapping[e]
	mid = (start+end)//2
	if (l[mid] == e):
		mapping[e] = (e, e)
		return mapping[e]
	elif (l[mid] > e):
		if (l[mid-1] < e):
			mapping[e] = (l[mid-1], l[mid])
			return mapping[e]
		return find(l, e, start, mid)
	elif (l[mid] < e):
		if (l[mid+1] > e):
			mapping[e] =  (l[mid], l[mid+1])
			return mapping[e]
		return find(l, e, mid, end)

def print_sum(input):
	d, n, m = input[0], input[1], input[2]
	S, K = input[3:3+n-1], input[3+n-1:]
	S = sorted(S)
	S = [S[-1]-d, 0] + S + [d]
	sum = 0
	for k in K:
		low, high = find(S, k, 0, len(S))
		sum += min(k-low, high-k)
	print sum

while (True):
	d = int(raw_input())
	if d == 0: break
	n, m = int(raw_input()), int(raw_input())
	input = [d, n, m]
	for i in range(n-1+m):
		next_int = int(raw_input())
		input.append(next_int)
	print_sum(input)

Submission status: Wrong Answer

Solution code:
import bisect
d = int(input())
n = int(input())
m = int(input())

shops = [0]*n
for i in range(1,n):
    shops[i] = int(input())
shops.sort()
shops.append(d)
d = 0
for i in range(m):
    cus = int(input())
    req = bisect.bisect(shops,cus)
    d += min(abs(cus-shops[req-1]), abs(cus-shops[req]))

print(d)

Submission status: Wrong Answer

Solution code:
while(True):
    D=int(input())
    if D==0:
        break
    N=int(input())
    M=int(input())
    d=[0 for i in range(N)]
    for i in range(1,N):
        d[i]=int(input())
    d.append(D)
    d.sort()
    k=[int(input()) for p in range(M)]
    ans=0
    for p in range(M):
        if k[p]==0:
            continue
        elif k[p]==D-1:
            if d[N-1]==D-1:
                continue
            else:
                ans+=1
                continue
        #binarysearch
        low=0
        high=N
        t=(low+high)//2
        if 0<=t-1 and d[t-1]<=k[p]<=d[t]:
            ans+=min(k[p]-d[t-1],d[t]-k[p])
            continue
        elif t+1<=N and d[t]<=k[p]<=d[t+1]:
            ans+=min([d[t+1]-k[p],k[p]-d[t]])
            continue
        while(low<=high):
            if d[t]<k[p]:
                low=t
            elif d[t]>k[p]:
                high=t-1
            else:
                break
            t=(low+high)//2
            if (high-low)<=1:
                if d[low]==k[p]:
                    break
                elif d[high]==k[p]:
                    break
                else:
                    ans+=(min([abs(d[high]-k[p]),abs(k[p]-d[low])]))
                    break
    print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left as bs
def solve():
  while True:
    d = int(input())
    if not d: break
    n = int(input())
    m = int(input())
    d_lst = [int(input()) for _ in range(n - 1)]
    d_lst.extend([0,d])
    d_lst.sort()
    ans = 0
    for _ in range(m):
      k = int(input())
      ind = bs(d_lst,k)
      ans += min(d_lst[ind] - k, k - d_lst[ind - 1])
    print(ans)
solve()

Submission status: Wrong Answer

Solution code:
# AOJ 0539: Pizza
# Python3 2018.7.1 bal4u

import bisect

while True:
	d = int(input())
	if d == 0: break
	n, m = int(input()), int(input())
	p = [0] + [int(input()) for i in range(n-1)] + [d]
	p.sort()
	ans = 0
	for i in range(m):
		k = int(input())
		t = bisect.bisect_left(p, k)
		ans += min(k-p[t-1], p[t]-k)
	print(ans)

Submission status: Wrong Answer

Solution code:
d=input()
n=input()
m=input()
shops = [0]
for i in xrange(n-1):
    shops.append(input())
shops.sort(cmp=None, key=None, reverse=False)
orders = []
for i in xrange(m):
    orders.append(input())
orders.sort(cmp=None, key=None, reverse=False)
sigRoute = 0
for order in orders:
    minRoute = d
    for shop in shops:
        if shop == order:
            minRoute = 0
        if shop < order:
            if minRoute >= abs(order - shop):
                minRoute = abs(order - shop)
            if minRoute > abs(d+shop - order):
                minRoute = abs(d+shop - order)
        elif order < shop:
            if minRoute >= abs(shop - order):
                minRoute = abs(shop - order)
            if minRoute > abs(d+order - shop):
                minRoute = abs(d+order - shop)
    sigRoute += minRoute
print sigRoute

Submission status: Time Limit Exceeded

Solution code:
def print_sum(input):
	d, n, m = input[0], input[1], input[2]
	S, K = set([0]+input[3:3+n-1]), input[3+n-1:]
	sum = 0
	for k in K:
		i = 0
		while (True):
			if (k+i)%d in S or (k-i)%d in S: break
			i += 1
		sum += i
	print sum
while (True):
	d = int(raw_input())
	if d == 0: break
	n, m = int(raw_input()), int(raw_input())
	input = [d, n, m]
	for i in range(n-1+m):
		next_int = int(raw_input())
		input.append(next_int)
	print_sum(input)

Submission status: Time Limit Exceeded

Solution code:
import bisect

while True:
	d = input()
	if d == 0: break
	n = input()
	m = input()
	shops = [0, 0]
	for i in xrange(n - 1):
		bisect.insort_left(shops, input())
	bisect.insort_left(shops, d)
	res = 0
	for i in xrange(m):
		x = input()
		p = bisect.bisect_left(shops[1:], x) + 1
		res += min(shops[p] - x, x - shops[p - 1]);
	print res

Submission status: Time Limit Exceeded

Solution code:
import bisect

while True:
	d = input()
	if d == 0: break
	n = int(raw_input())
	m = int(raw_input())
	shops = [0, 0]
	for i in xrange(n - 1):
		bisect.insort_left(shops, input())
	bisect.insort_left(shops, d)
	res = 0
	for i in xrange(m):
		x = input()
		p = bisect.bisect_left(shops[1:], x) + 1
		res += min(shops[p] - x, x - shops[p - 1]);
	print res

Submission status: Time Limit Exceeded

Solution code:
ans = []
while True:
    d=input()
    if d == 0:
        break
    n=input()
    m=input()
    shops = [0]
    for i in xrange(n-1):
        shops.append(input())
    shops.sort(cmp=None, key=None, reverse=False)
    orders = []
    for i in xrange(m):
        orders.append(input())
    orders.sort(cmp=None, key=None, reverse=False)
    sigRoute = 0
    for order in orders:
        minRoute = d
        for shop in shops:
            if shop == order:
                minRoute = 0
            if shop < order:
                if minRoute >= abs(order - shop):
                    minRoute = abs(order - shop)
                if minRoute > abs(d+shop - order):
                    minRoute = abs(d+shop - order)
            elif order < shop:
                if minRoute >= abs(shop - order):
                    minRoute = abs(shop - order)
                if minRoute > abs(d+order - shop):
                    minRoute = abs(d+order - shop)
        sigRoute += minRoute
    ans.append(sigRoute)

for i in ans:
    print i

Submission status: Accepted

Solution code:
read = map(int, open(0).readlines()).__next__
ans = []
while 1:
    D = read()
    if D == 0:
        break
    N = read()
    M = read()
    P = [read() for i in range(N-1)]
    P.append(0); P.append(D)
    Q = [read() for i in range(M)]

    P.sort(); Q.sort()
    it = iter(P).__next__
    prv = 0; nxt = it(); idx = 0
    res = 0
    for q in Q:
        while nxt <= q:
            prv = nxt; nxt = it()
        res += min(q - prv, nxt - q)
    ans.append("%d\n" % res)
open(1, 'w').writelines(ans)

Submission status: Accepted

Solution code:
import bisect
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


def solve():
    d = int(input())
    if d == 0:
        return False
    n = int(input())
    m = int(input())
    stores = [int(input()) for _ in range(n-1)]
    stores = [0]+sorted(stores)+[d]

    ret = 0
    for _ in range(m):
        dest = int(input())
        l = bisect.bisect_right(stores, dest)
        dist = min(stores[l]-dest, dest-stores[l-1])
        ret += dist
    return ret


ans = []
while True:
    a = solve()
    if a:
        ans.append(a)
    else:
        break
print("\n".join(map(str, ans)))

Submission status: Accepted

Solution code:
from bisect import bisect_left
while 1:
    d = input()
    if d == 0: break
    n = input()
    m = input()
    s = [input() for i in range(n-1)]
    s += [0]
    s.sort()
    ans = 0
    for i in range(m):
        t = input()
        j = bisect_left(s, t)
        if j == n: ans += min(t-s[n-1], d-t)
        elif j == 0: continue
        else: ans += min(t-s[j-1], s[j]-t)
    print ans

Submission status: Accepted

Solution code:
from bisect import bisect_left

while True:
    d = int(input())
    if not d:
        break
    n = int(input())
    m = int(input())
    stores = {0, d}
    for i in range(2, n + 1):
        stores.add(int(input()))
    sorted_stores = sorted(stores)

    total_dist = 0
    while m:
        k = int(input())
        i = bisect_left(sorted_stores, k)
        if i:
            l, r = sorted_stores[i - 1:i + 1]
            total_dist += min(k - l, r - k)
        m -= 1
    print(total_dist)

Submission status: Accepted

Solution code:
import bisect

def solve():
    n=int(raw_input())
    m=int(raw_input())
    dist=[0]+[int(raw_input()) for _ in xrange(n-1)]+[d]
    q=[int(raw_input()) for _ in xrange(m)]
    dist.sort();

    ans=0
    for i in q:
        if bisect.bisect_left(dist,i)==n:
            l=n-1
        else:
            l=bisect.bisect_left(dist,i)
            if dist[l]!=i:
                l-=1
        r=bisect.bisect_left(dist,i)
        ans+=min(i-dist[l],dist[r]-i)

    return ans

while 1:
    d=int(raw_input())
    if d==0:break
    ans=solve()
    print ans

Submission status: Accepted

Solution code:
import bisect

def solve():
    n=int(raw_input())
    m=int(raw_input())
    dist=[0]+[int(raw_input()) for _ in xrange(n-1)]+[d]
    q=[int(raw_input()) for _ in xrange(m)]
    dist.sort();

    ans=0
    for i in q:
        l=bisect.bisect_left(dist,i)
        if dist[l]==i:continue
        l-=1
        r=bisect.bisect_left(dist,i)
        ans+=min(i-dist[l],dist[r]-i)

    return ans

while 1:
    d=int(raw_input())
    if d==0:break
    ans=solve()
    print ans

Submission status: Accepted

Solution code:
import bisect

def solve():
    n=int(raw_input())
    m=int(raw_input())
    dist=[0]+[int(raw_input()) for _ in xrange(n-1)]+[d]
    dist.sort();

    ans=0
    for i in xrange(m):
        q=int(raw_input())
        l=bisect.bisect_left(dist,q)-1
        r=bisect.bisect_left(dist,q)
        ans+=min(abs(q-dist[l]),abs(dist[r]-q))

    return ans

while 1:
    d=int(raw_input())
    if d==0:break
    ans=solve()
    print ans

Submission status: Accepted

Solution code:
import bisect

while(1):
    d=int(raw_input())
    if d==0: break
    n=int(raw_input())
    m=int(raw_input())
    L=[0,d]
    for i in range(n-1):
        a=int(raw_input())
        L+=[a]
    L.sort()
    ans=0
    for j in range(m):
        a=int(raw_input())
        if a!=0:
            ind=bisect.bisect(L,a)
            ans+=min(abs(L[ind]-a),abs(L[ind-1]-a))
    print ans

Submission status: Accepted

Solution code:
def find(l, e, start, end):
	mid = (start+end)//2
	if (l[mid] == e):
		return (e, e)
	elif (l[mid] > e):
		if (l[mid-1] < e): 
			return (l[mid-1], l[mid])
		return find(l, e, start, mid)
	elif (l[mid] < e):
		if (l[mid+1] > e): 
			return (l[mid], l[mid+1])
		return find(l, e, mid, end)

def print_sum(input):
	d, n, m = input[0], input[1], input[2]
	S, K = input[3:3+n-1], input[3+n-1:]
	S = [max(S)-d, 0] + sorted(S)+ [d]
	sum = 0
	for k in K:
		low, high = find(S, k, 0, len(S))
		sum += min(k-low, high-k)
	print sum

while (True):
	d = int(raw_input())
	if d == 0: break
	n, m = int(raw_input()), int(raw_input())
	input = [d, n, m]
	for i in range(n-1+m):
		next_int = int(raw_input())
		input.append(next_int)
	print_sum(input)

Submission status: Accepted

Solution code:
def find(l, e, start, end):
	mid = (start+end)//2
	if (l[mid] == e):
		return (e, e)
	elif (l[mid] > e):
		if (l[mid-1] < e): 
			return (l[mid-1], l[mid])
		return find(l, e, start, mid)
	elif (l[mid] < e):
		if (l[mid+1] > e): 
			return (l[mid], l[mid+1])
		return find(l, e, mid, end)

def print_sum(input):
	d, n, m = input[0], input[1], input[2]
	S, K = input[3:3+n-1], input[3+n-1:]
	S = sorted(S)
	S = [S[-1]-d, 0] + S + [d]
	sum = 0
	for k in K:
		low, high = find(S, k, 0, len(S))
		sum += min(k-low, high-k)
	print sum

output = []
while (True):
	d = int(raw_input())
	if d == 0: break
	n, m = int(raw_input()), int(raw_input())
	input = [d, n, m]
	for i in range(n-1+m):
		next_int = int(raw_input())
		input.append(next_int)
	print_sum(input)

Submission status: Accepted

Solution code:
mapping = {}
def find(l, e, start, end):
	global mapping
	if e in mapping:
		return mapping[e]
	mid = (start+end)//2
	if (l[mid] == e):
		mapping[e] = (e, e)
		return mapping[e]
	elif (l[mid] > e):
		if (l[mid-1] < e):
			mapping[e] = (l[mid-1], l[mid])
			return mapping[e]
		return find(l, e, start, mid)
	elif (l[mid] < e):
		if (l[mid+1] > e):
			mapping[e] =  (l[mid], l[mid+1])
			return mapping[e]
		return find(l, e, mid, end)

def print_sum(input):
	global mapping
	mapping = {}
	d, n, m = input[0], input[1], input[2]
	S, K = input[3:3+n-1], input[3+n-1:]
	S = sorted(S)
	S = [S[-1]-d, 0] + S + [d]
	sum = 0
	for k in K:
		low, high = find(S, k, 0, len(S))
		sum += min(k-low, high-k)
	print sum

while (True):
	d = int(raw_input())
	if d == 0: break
	n, m = int(raw_input()), int(raw_input())
	input = [d, n, m]
	for i in range(n-1+m):
		next_int = int(raw_input())
		input.append(next_int)
	print_sum(input)

Submission status: Accepted

Solution code:
def find(l, e, start, end):
	mid = (start+end)//2
	if (l[mid] == e):
		return (e, e)
	elif (l[mid] > e):
		if (l[mid-1] < e):
			return (l[mid-1], l[mid])
		return find(l, e, start, mid)
	elif (l[mid] < e):
		if (l[mid+1] > e):
			return (l[mid], l[mid+1])
		return find(l, e, mid, end)

def print_sum(input):
	d, n, m = input[0], input[1], input[2]
	S, K = input[3:3+n-1], input[3+n-1:]
	S = sorted(S)
	S = [S[-1]-d, 0] + S + [d]
	sum = 0
	for k in K:
		low, high = find(S, k, 0, len(S))
		sum += min(k-low, high-k)
	print sum

while (True):
	d = int(raw_input())
	if d == 0: break
	n, m = int(raw_input()), int(raw_input())
	input = [d, n, m]
	for i in range(n-1+m):
		next_int = int(raw_input())
		input.append(next_int)
	print_sum(input)

Submission status: Accepted

Solution code:
def find(l, e, start, end):
	mid = (start+end)//2
	if (l[mid] == e):
		return (e, e)
	elif (l[mid] > e):
		if (l[mid-1] < e):
			return (l[mid-1], l[mid])
		return find(l, e, start, mid)
	elif (l[mid] < e):
		if (l[mid+1] > e):
			return (l[mid], l[mid+1])
		return find(l, e, mid, end)

def print_sum(input):
	d, n, m = input[0], input[1], input[2]
	S, K = input[3:3+n-1], input[3+n-1:]
	S = [0] + sorted(S) + [d]
	sum = 0
	for k in K:
		low, high = find(S, k, 0, len(S))
		sum += min(k-low, high-k)
	print sum

while (True):
	d = int(raw_input())
	if d == 0: break
	n, m = int(raw_input()), int(raw_input())
	input = [d, n, m]
	for i in range(n-1+m):
		next_int = int(raw_input())
		input.append(next_int)
	print_sum(input)

Submission status: Accepted

Solution code:
def find(l, e, start, end):
	mid = (start+end)//2
	if (l[mid] == e):
		return (e, e)
	elif (l[mid] > e):
		if (l[mid-1] < e):
			return (l[mid-1], l[mid])
		return find(l, e, start, mid)
	elif (l[mid] < e):
		if (l[mid+1] > e):
			return (l[mid], l[mid+1])
		return find(l, e, mid, end)

def print_sum():
	d = int(raw_input())
	if d == 0: return False
	n, m = int(raw_input()), int(raw_input())
	S = [int(raw_input()) for _ in range(n-1)]
	K = [int(raw_input()) for _ in range(m)]
	S = [0] + sorted(S) + [d]
	sum = 0
	for k in K:
		low, high = find(S, k, 0, len(S))
		sum += min(k-low, high-k)
	print sum
	return True

while (print_sum()):
	pass

Submission status: Accepted

Solution code:
def find(l, e):
	start, end = 0, len(l)
	while True:
		mid = (start+end)//2
		if l[mid] == e: 
			return (e, e)
		elif (l[mid] > e):
			if (l[mid-1] < e):
				return (l[mid-1], l[mid])
			end = mid
			continue
		elif (l[mid] < e):
			if (l[mid+1] > e):
				return (l[mid], l[mid+1])
			start = mid

def print_sum():
	d = int(raw_input())
	if d == 0: return False
	n, m = int(raw_input()), int(raw_input())
	S = [int(raw_input()) for _ in range(n-1)]
	K = [int(raw_input()) for _ in range(m)]
	S = [0] + sorted(S) + [d]
	sum = 0
	for k in K:
		low, high = find(S, k)
		sum += min(k-low, high-k)
	print sum
	return True

while (print_sum()):
	pass

Submission status: Accepted

Solution code:
def print_sum():
	d = int(raw_input())
	if d == 0: return False
	n, m = int(raw_input()), int(raw_input())
	S = [int(raw_input()) for _ in range(n-1)]
	K = sorted([int(raw_input()) for _ in range(m)], reverse=True)
	S = sorted(S) + [d]
	S_k = [[] for _ in range(len(S))]
	for i, s in enumerate(S):
		for j in range(len(K)-1, -1, -1):
			if K[j] <= s:
				S_k[i].append(K.pop())
			else:
				break
	sum = 0
	S = [0] + S
	for i, sk in enumerate(S_k):
		for k in sk:
			sum += min(k-S[i], S[i+1]-k)
	print sum
	return True

while print_sum():
	pass

Submission status: Accepted

Solution code:
import bisect
while True:
    d = int(input())
    if d==0: break
    n = int(input())
    m = int(input())

    shops = [0]*n
    for i in range(1,n):
        shops[i] = int(input())
    shops.sort()
    shops.append(d)
    d = 0
    for i in range(m):
        cus = int(input())
        req = bisect.bisect(shops,cus)
        d += min(abs(cus-shops[req-1]), abs(cus-shops[req]))

    print(d)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0539

"""
import sys
from sys import stdin
from bisect import bisect_right
input = stdin.readline



def main(args):
    while True:
        d = int(input())        #  ??°??¶????????????
        if d == 0:
            break
        n = int(input())        #  ??¬????????????????????°
        m = int(input())        #  ??¨????????°
        cw_pos = [int(input()) for _ in range(n-1)]
        dests = [int(input()) for _ in range(m)]

        cw_pos.append(0)
        cw_pos.append(d)
        cw_pos.sort()

        ccw_pos = [d-x for x in cw_pos]
        ccw_pos.sort()


        total_distance = 0
        for t in dests:
            if t == 0:
                continue
            i = bisect_right(cw_pos, t)
            a1 = min(t-cw_pos[i-1], cw_pos[i]-t)

            j = bisect_right(ccw_pos, d-t)
            a2 = min(d-t-ccw_pos[j-1], ccw_pos[j]-(d-t))

            ans = min(a1, a2)
            total_distance += ans

        print(total_distance)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0539
AC
"""
import sys
from sys import stdin
from bisect import bisect_right
input = stdin.readline


def main(args):
    while True:
        d = int(input())        #  ??°??¶????????????
        if d == 0:
            break
        n = int(input())        #  ??¬????????????????????°
        m = int(input())        #  ??¨????????°
        cw_pos = [int(input()) for _ in range(n-1)]
        dests = [int(input()) for _ in range(m)]

        cw_pos.append(0)        #  ??¬????????????
        cw_pos.append(d)        #  ??°??¶??????1??¨??????????????¬????????????(??????)
        cw_pos.sort()

#        ccw_pos = [d-x for x in cw_pos] #  ??°??¶?????????????????£????????????????????????
#        ccw_pos.sort()


        total_distance = 0
        for t in dests:
            if t == 0:          #  ?????????????????????0?????\??£????????????bisect_right?????¨????????????????????§??????
                continue
            i = bisect_right(cw_pos, t)          #  ????¨?????????§??????????????????
            a1 = min(t-cw_pos[i-1], cw_pos[i]-t) #  ?????????????????????????????¢

#            j = bisect_right(ccw_pos, d-t)       #  ???????¨?????????§???????????¨?????????
#            a2 = min(d-t-ccw_pos[j-1], ccw_pos[j]-(d-t))

#            ans = min(a1, a2)
            total_distance += a1 #  ?????????????????????????????°OK

        print(total_distance)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

Solution code:
import sys

file_input = sys.stdin
d = int(file_input.readline())

import bisect

def calc_distance(destination):
    p = bisect.bisect(shop, destination)
    d1 = shop[p] - destination
    d2 = destination - shop[p - 1]
    return min(d1, d2)

while d:
    n = int(file_input.readline())
    m = int(file_input.readline())
    shop = [int(file_input.readline()) for i in range(n - 1)]
    shop.append(0)
    shop.append(d)
    shop.sort()
    k = (int(file_input.readline()) for i in range(m))
    ans = sum(map(calc_distance, k))
    print(ans)
    d = int(file_input.readline())

Submission status: Accepted

Solution code:
import bisect
def main():
	while True:
		D=int(input())
		if D==0:
			break
		n=int(input())
		m=int(input())
		d=list()
		d.append(0)
		for i in range(n-1):
			d.append(int(input()))
		d.append(D)
		d.sort()
		ans=0
		for i in range(m):
			k=int(input())
			idx=bisect.bisect_left(d,k)
			ans+=min(abs(d[idx]-k),abs(d[idx-1]-k))
		print(ans)

if __name__=="__main__":
	main()

Submission status: Accepted

Solution code:
import bisect
    
def main():
    while True:
        d = int(input())
        if d == 0:
            break
        n = int(input())
        m = int(input())
        s = [0] + [int(input()) for i in range(n - 1)] + [d]
        s.sort()
        
        print(sum(dist(s, int(input())) for i in range(m)))

def dist(s, o):
    return min(o- s[bisect.bisect_right(s, o) - 1], s[bisect.bisect_left(s,o)] - o)
        
if __name__=="__main__":
	main()

Submission status: Accepted

Solution code:
import bisect
    
def main():
    while True:
        d = int(input())
        if d == 0:
            break
        n = int(input())
        m = int(input())
        s = [0] + [int(input()) for i in range(n - 1)] + [d]
        s.sort()
        
        print(sum(dist(s, int(input())) for i in range(m)))

def dist(s, o):
    i = bisect.bisect_right(s, o)
    return min(o- s[i - 1], s[i] - o)
        
if __name__=="__main__":
	main()

Submission status: Accepted

Solution code:
from bisect import bisect_left as bs
while True:
  d = int(input())
  if not d: break
  n = int(input())
  m = int(input())
  d_lst = [int(input()) for _ in range(n - 1)]
  k_lst = [int(input()) for _ in range(m)]
  d_lst.extend([0,d])
  d_lst.sort()
  ans = 0
  for k in k_lst:
    ind = bs(d_lst,k)
    ans += min(abs(k - d_lst[ind]), abs(k - d_lst[ind - 1]))
  print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left as bs
def solve():
  while True:
    d = int(input())
    if not d: break
    n = int(input())
    m = int(input())
    d_lst = [int(input()) for _ in range(n - 1)]
    d_lst.extend([0,d])
    d_lst.sort()
    ans = 0
    for _ in range(m):
      k = int(input())
      ind = bs(d_lst,k)
      ans += min(abs(k - d_lst[ind]), abs(k - d_lst[ind - 1]))
    print(ans)
solve()

Submission status: Accepted

Solution code:
# AOJ 0539: Pizza
# Python3 2018.7.1 bal4u

import bisect

while True:
	d = int(input())
	if d == 0: break
	n, m = int(input()), int(input())
	p = [0] + [int(input()) for i in range(n-1)] + [d]
	p.sort()
	ans = 0
	for i in range(m):
		k = int(input())
		if k > 0:
			t = bisect.bisect_left(p, k)
			ans += min(k-p[t-1], p[t]-k)
	print(ans)

Submission status: Accepted

Solution code:
# AOJ 0539: Pizza
# Python3 2018.7.1 bal4u

import sys
from sys import stdin
input = stdin.readline
import bisect

while True:
	d = int(input())
	if d == 0: break
	n, m = int(input()), int(input())
	p = [0] + [int(input()) for i in range(n-1)] + [d]
	p.sort()
	ans = 0
	for i in range(m):
		k = int(input())
		if k > 0:
			t = bisect.bisect_left(p, k)
			ans += min(k-p[t-1], p[t]-k)
	print(ans)

Submission status: Accepted

Solution code:
import bisect

while True:

  d = int(raw_input())

  if d == 0:
    break

  n = int(raw_input())
  m = int(raw_input())

  store = []
  store.append(0)
  store.append(d)

  for x in xrange(n - 1):
    s = int(raw_input())
    store.append(s)

  store.sort()

  ans = 0

  # print repr(store)

  for x in xrange(m):
    p = int(raw_input())

    l = bisect.bisect_right(store, p) - 1
    r = bisect.bisect_right(store, p)

    l_ = store[l]
    r_ = store[r]

    # print 'log L:%d R:%d p:%d' % (l_, r_, p)

    t = min(abs(p - l_), abs(p - r_))
    ans += t

  print ans

Submission status: Accepted

Solution code:
while True:
  D = int(input())
  if D==0: exit()
  N = int(input())
  M = int(input())
  shops = [0]
  for _ in range(N-1):
    shops.append(int(input()))
  shops.append(D)
  shops.sort()

  res = 0
  for _ in range(M):
    x = int(input())
    ok,ng = -1,len(shops)
    while abs(ok-ng)>1:
      mid = (ok+ng)//2
      if shops[mid] <= x:
        ok = mid
      else:
        ng = mid
    res += min(x-shops[ok], shops[ok+1]-x)

  print(res)

Submission status: Accepted

Solution code:
def search_min_route(d,n_list,m_list):
	result = 0
	n_list.sort()
	n_list.append(d)
	for m in m_list:
		result += bs_min(n_list,m)

	return result

def bs_min(n_list,m):
	left = 0
	right = len(n_list)-1
	count = 0
	while abs(right - left) != 1:
		mid = int((right - left)/2 + left)
		if n_list[mid] == m:
			return 0
		elif n_list[mid] > m:
			right = mid
		else:
			left = mid
		count += 1

	return min(abs(n_list[left]-m),abs(n_list[right]-m))


def main():
	#データの入力
	data_list = []
	d = int(input())
	while d != 0:
		n = int(input())
		m = int(input())
		n_list = []
		m_list = []
		n_list.append(0)
		for i in range(n-1):
			n_list.append(int(input()))

		for i in range(m):
			m_list.append(int(input()))

		new_list = [d,n,m,n_list,m_list]
		data_list.append(new_list)
		d = int(input())

	for data in data_list:
		print(search_min_route(data[0],data[3],data[4]))
		
		
if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
#B
while True:
    import bisect
    L = int(input()) #length
    if L == 0:
        break
    N = int(input())
    M = int(input())

    D = [int(input()) for i in range(N-1)]
    K = [int(input()) for i in range(M)]

    Md = max(D)
    D.append(0)
    D.append(L)
    D.sort()
    #print(D)
    ans = 0
    for k in K:
        ind = bisect.bisect_left(D,k)
        #print(ind)
        ans+=min(abs(k-D[ind]),abs(k-D[ind-1]))

    print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left

while True:
    line = input()
    if line == '0':
        break

    d = int(line)  # 環状線の全長
    n = int(input())  # ピザの店舗の個数
    m = int(input())  # 注文の個数
    D = []

    for i in range(n - 1):
        D.append(int(input()))

    D += [0, d]
    D.sort()

    ans = 0

    for i in range(m):
        k = int(input())
        j = bisect_left(D, k)
        ans += min(abs(k - D[j - 1]), abs(k - D[j]))

    print(ans)

Submission status: Accepted

Solution code:
import bisect,sys

while True:
    d = int(input())

    if d == 0 : break

    n = int(input())
    m = int(input())

    dis = [0]

    for i in range(n-1):
        dd = int(input())
        dis.append(dd)

    dis.sort()
    ans = 0
    for i in range(m):
        kk = int(input())
        pt = bisect.bisect_right(dis,kk)
        if (pt < n):
            ans += min(dis[pt]-kk ,kk - dis[pt-1])
        else :
            ans += min(kk - dis[pt-1],d-kk)

    print(ans)

Submission status: Accepted

Solution code:
import bisect
while True:
    len_d = int(input())
    if len_d == 0: break
    n = int(input())
    m = int(input())
    d = [0]
    k = []
    for i in range(1, n):
         d.append(int(input()))
    for i in range(m):
         k.append(int(input()))
    d.sort()
    c = [len_d for i in range(m)]
    ans = 0
    for i in range(m):
        if k[i] == 0: continue
        t = bisect.bisect_left(d, k[i])
        if t == n:
            ans += min(len_d-k[i], k[i]-d[n-1])
        else:
            ans += min(k[i]-d[t-1], d[t]-k[i])
    print(ans)