Problem:


Problem 05: Split Up!

勇者ポン太とその親友同じく勇者ゴン太は、これから壮大な冒険へと出発するために、それぞれ仲間を求めてルイーダの酒場へやって来ました。酒場には、冒険に出たくてうずうずしている武闘家や僧侶、魔法使いがたくさん居ます。

心やさしいゴン太はポン太を気遣い、「先に仲間を選んでいいよ。」と言いました。

一方、ポン太もゴン太が心配でなりません。「いや、君が先に選んでいいよ。」と言い返しました。

お互い譲り合いが続き、ついにルイーダがこう提案しました。「じゃあ、ここにいる n 人の登録者をそれぞれのパーティの合計戦闘力がなるべく均等になるように、この"パーティ分けマシン"で分けてあげるわ。」

あなたに与えられた仕事は、パーティ分けマシンに組み込まれているプログラムを作成することです。

このプログラムは　n 個の整数を入力し、それらを２つのグループ A, B に分けたときの、A に含まれる整数の合計値と B に含まれる整数の合計値の差の最小値を出力しなければなりません。

このマシンのおかげで、ポン太とゴン太は仲良く仲間を見つけ、壮大な冒険へと出かけて行きました・・。

Input

入力として複数のデータセットが与えられます。各データセットは以下の形式で与えられます：

n (登録者の数： 整数)

a1 a2 ... an　（各登録者の戦闘力： 空白区切りの整数）

n は 20 以下であり、各登録者の戦闘力は 100 万を越えません。

n が 0 のとき入力の終わりとします。

Output

各データセットに対して、最小値を1行に出力して下さい。

Sample Input

5
1 2 3 4 5
4
2 3 5 7
0

Output for the Sample Input

1
1



Sample input:
5
1 2 3 4 5
4
2 3 5 7
0


Sample output:
1
1

Submission status: Wrong Answer

Solution code:
# AOJ 1045: Split Up!
# Python3 2018.7.6 bal4u

while True:
	n = int(input())
	if n == 0: break
	t = list(map(int, input().split()))
	s = sum(t)
	ans = s >> 1
	a, f = [], True
	for v in t:
		if v == ans:
			f = False
			break
		if v < ans: a.append(v)
	if f:
		S, Q = set(), [0]
		for v in a:
			while Q:
				v2 = v + Q.pop(0)
				if v2 == ans:
					f = False
					break
				if v2 < ans and v2 not in S:
					S.add(v2)
					Q.append(v2)
	if f:
		while ans > 1:
			ans -= 1
			if ans in S: break;
	print(s - 2*ans)

Submission status: Wrong Answer

Solution code:
while(1):
    n=int(raw_input())
    if n==0:
        break
    else:
        s=[int(x) for x in raw_input().split()]
        s.sort(reverse=True)
        a=0
        b=0
        for c in s:
            if a>b:
                b+=c
            else:
                a+=c
        print abs(a-b)

Submission status: Wrong Answer

Solution code:
while 1:
    n = input()
    if n == 0: break
    a = map(int, raw_input().split())
    x = 0
    for i in range(n):
        if (a[i] < a[x]):
            x = i
    print x + 1

Submission status: Wrong Answer

Solution code:
while 1:
    n=int(input())
    if n==0:break
    m=sorted(map(int,input().split()),reverse=1)
    a=b=0
    print(m)
    for i in m:
        if a>b:b+=i
        else: a+=i
    print(abs(a-b))

Submission status: Wrong Answer

Solution code:
while 1:
    n=int(input())
    if n==0:break
    m=sorted(map(int,input().split()),reverse=1)
    a=b=0
    for i in m:
        if a>b:b+=i
        else: a+=i
    print(abs(a-b))

Submission status: Wrong Answer

Solution code:
while(1):
    n=int(raw_input())
    if n==0: break
    A=sorted(map(int,raw_input().split()), reverse=True)
    S=sum(A)
    anslist=[]
    for a in A:
        if S>=2*a:
            S-=2*a
        else:
            anslist.append(abs(S-2*a))
    print min(anslist)

Submission status: Wrong Answer

Solution code:
import itertools
while 1:
	n = input()
	if n == 0: break
	s = sorted(map(int,raw_input().split()))
	sm1 = ans = sum(s)
	for i in range(1,n-1):
		for party in itertools.combinations(s,i):
			print party
			sm2 = sm1 - 2*sum(party)
			if sm2 < -ans: break
			ans = min(ans,abs(sm2))
	print ans

Submission status: Wrong Answer

Solution code:
import itertools
while 1:
	n = input()
	if n == 0: break
	s = sorted(map(int,raw_input().split()))
	sm1 = ans = sum(s)
	for i in range(1,n-1):
		for party in itertools.combinations(s,i):
			sm2 = sm1 - 2*sum(party)
			if sm2 < -ans: break
			ans = min(ans,abs(sm2))
	print ans

Submission status: Wrong Answer

Solution code:
import itertools
while 1:
	try:
		n = input()
		if n == 0: break
		s = sorted(map(int,raw_input().split()))
		sm = sum(s)
		for i in range(1,n-1):
			ans = sorted(abs(sm - 2*sum(party)) for party in itertools.combinations(s,i))[0]
			if ans == 0: break
		print ans
	except:
		break

Submission status: Wrong Answer

Solution code:
import itertools
while 1:
	n = input()
	if n == 0: break
	s = sorted(map(int,raw_input().split()))
	sm = ans = sum(s)
	for i in range(1,(n+1)/2+1):
		for party in itertools.combinations(s,i):
			cur = sm - 2*sum(party)
			if cur < -ans: break
			ans = min(ans,abs(cur))
	print ans

Submission status: Wrong Answer

Solution code:
import itertools
while 1:
	n = input()
	if n == 0: break
	s = sorted(map(int,raw_input().split()))
	sm = sum(s)
	dp = [0] * sm
	for i in s:
		dp[i] = i
	for i in s:
		for j in range(sm):
			if dp[j] > 0 and dp[j] != i:
				try: dp[j+i] = dp[j] + i
				except: break
	print min([abs(sm-dp[i]) for i in range(sm)])

Submission status: Wrong Answer

Solution code:
while 1:
	n = input()
	if n == 0: break
	s = map(int,raw_input().split())
	sm = sum(s)
	dp = [0] * (sm+1)
	for i in s:
		dp[i] = i
	for i in s:
		for j in range(sm+1):
			if dp[j] > 0 and j != i:
				try: dp[j+i] = dp[j] + i
				except: break
	print min([abs(sm-dp[i]) for i in range(sm)])

Submission status: Wrong Answer

Solution code:
while 1:
	n = input()
	if n == 0: break
	s = map(int,raw_input().split())
	sm = sum(s)
	dp = [0] * (sm+1)
	for i in s:
		dp[i] = i
	for i in s:
		for j in range(sm+1):
			if dp[j] > 0 and j != i:
				try: dp[j+i] = dp[j] + i
				except: break
	print min([abs(sm-2*dp[i]) for i in range(sm)])

Submission status: Wrong Answer

Solution code:
while 1:
	n = input()
	if n == 0: break
	a = sorted(map(int,raw_input().split()))[::-1]
	s = sum(a)
	L = [0]
	for i in a:
		L += [i+j for j in L if i < s/2 and j < s/2]
	print min(abs(s-2*i) for i in L)

Submission status: Time Limit Exceeded

Solution code:
m=[0]*20
d=1<<20
def f(a, b, c, n,):
    global d
    if c==n:d=min(d,abs(a-b));return
    f(a+m[c],b,c+1,n)
    f(a,b+m[c],c+1,n)
    return (d)
while 1:
    n=int(input())
    if n==0:break
    m=sorted(map(int,input().split()),reverse=1)
    print(f(0,0,0,n))

Submission status: Time Limit Exceeded

Solution code:
import itertools
while True:
    n=input()
    if n==0:break
    L=map(int,raw_input().split())
    total=sum(L)
    diff=10000000000
    for i in range(1,n+1):
        for comb in itertools.combinations(L,i):
            part=sum(comb)
            diff=min(diff,abs(total-2*part))
    print diff

Submission status: Time Limit Exceeded

Solution code:
def dfs(diff,k):
    global ans
    if k==n:
        ans=min(ans,abs(diff))
    else:
        dfs(diff+L[k],k+1)
        dfs(diff-L[k],k+1)

while True:
    n=input()
    if n==0:break
    L=map(int,raw_input().split())
    ans=10000000000
    dfs(0,0)
    print ans

Submission status: Time Limit Exceeded

Solution code:
import itertools
while 1:
	n = input()
	if n == 0: break
	s = map(int,raw_input().split())
	sm = ans = sum(s)
	for i in range(1,n-1):
		for party in itertools.combinations(s,i):
			ans = min(ans,abs(sm-2*sum(party)))
	print ans

Submission status: Time Limit Exceeded

Solution code:
import itertools
while 1:
	n = input()
	if n == 0: break
	s = map(int,raw_input().split())
	sm = ans = sum(s)
	for i in range(1,n-1):
		for party in itertools.combinations(s,i):
			ans = min(ans,abs(sm-2*sum(party)))
			if ans == 0:
				break
	print ans

Submission status: Time Limit Exceeded

Solution code:
import itertools
while 1:
	n = input()
	if n == 0: break
	s = sorted(map(int,raw_input().split()))
	sm1 = ans = sum(s)
	for i in range(1,n-1):
		for party in sorted(itertools.combinations(s,i), key = lambda x:sum(x)):
			sm2 = sm1 - 2*sum(party)
			if sm2 < -ans: break
			ans = min(ans,abs(sm2))
	print ans

Submission status: Time Limit Exceeded

Solution code:
import itertools
while 1:
	n = input()
	if n == 0: break
	s = sorted(map(int,raw_input().split()))
	sm1 = ans = sum(s)
	for i in range(1,n-1):
		for party in sorted(itertools.combinations(s,i), key = lambda x:sum(x)):
			sm2 = sm1 - 2*sum(party)
			if sm2 < -ans: break
			ans = min(ans,abs(sm2))
			if ans == 0: break
	print ans

Submission status: Time Limit Exceeded

Solution code:
import itertools
while 1:
	try:
		n = input()
		if n == 0: break
		s = sorted(map(int,raw_input().split()))
		sm = sum(s)
		for i in range(1,n-1):
			ans = sorted(abs(sm - 2*sum(party)) for party in itertools.combinations(s,i))[0]
			if ans == 0: break
		print ans
	except:
		pass

Submission status: Time Limit Exceeded

Solution code:
import itertools
while 1:
	n = input()
	if n == 0: break
	s = sorted(map(int,raw_input().split()))
	sm = ans = sum(s)
	for i in range(1,n-1):
		for party in sorted(itertools.combinations(s,i)):
			sm1 = sm - 2*sum(party)
			if sm1 < -ans: break
			ans = min(ans,abs(sm1))
			if ans == 0: break
	print ans

Submission status: Time Limit Exceeded

Solution code:
import itertools
while 1:
	n = input()
	if n == 0: break
	s = sorted(map(int,raw_input().split()))
	sm = ans = sum(s)
	for i in range(1,n/2+1):
		for party in itertools.combinations(s,i):
			cur = sm - 2*sum(party)
			ans = min(ans,abs(cur))
	print ans

Submission status: Time Limit Exceeded

Solution code:
while 1:
	n = input()
	if n == 0: break
	s = map(int,raw_input().split())
	sm = sum(s)
	dp = [0] * (sm+1)
	ref = {i:[i] for i in s}
	for i in s:
		dp[i] = i
	for i in s:
		for j in range(sm+1):
			if dp[j] > 0 and j not in ref[i]:
				try:
					dp[j+i] = dp[j] + i
					ref[i].append(j + i)
				except: break
	print min([abs(sm-2*dp[i]) for i in range(sm)])

Submission status: Time Limit Exceeded

Solution code:
import itertools
while 1:
	n = input()
	if n == 0: break
	a = sorted(map(int,raw_input().split()))
	all = sum(a)
	ans = all
	for i in range((n+1)/2+1):
		c = 0
		for party in itertools.combinations(a,i):
			d = all-2*sum(party)
			if c == 0 and d < 0 and abs(d) > ans:
				break
			ans = min(ans,abs(d))
			c = 1
	print ans

Submission status: Time Limit Exceeded

Solution code:
import itertools
while 1:
	n = input()
	if n == 0: break
	a = sorted(map(int,raw_input().split()))
	all = sum(a)
	ans = all
	for i in range((n+1)/2+1):
		c = 0
		for party in itertools.combinations(a,i):
			d = all-2*sum(party)
			if c == 0 and d < -ans:
				break
			ans = min(ans,abs(d))
			c = 1
	print ans

Submission status: Time Limit Exceeded

Solution code:
def solve(a,i,sa,sb):
	if 2*sa >= all: return 2*sa-all
	if 2*sb >= all: return 2*sb-all
	return min(solve(a,i+1,sa+a[i],sb),solve(a,i+1,sa,sb+a[i]))
	
while 1:
	n = input()
	if n == 0: break
	a = sorted(map(int,raw_input().split()))
	all = sum(a)
	print solve(a,0,a[0],0)

Submission status: Time Limit Exceeded

Solution code:
while 1:
	n = input()
	if n == 0: break
	a = map(int,raw_input().split())
	ref = []
	for i in a:
		ref += [i+j for j in ref]
		ref.append(i)
	print min(abs(sum(a)-2*i) for i in ref)

Submission status: Time Limit Exceeded

Solution code:
while 1:
	n = input()
	if n == 0: break
	a = map(int,raw_input().split())
	ref = [0]
	for i in a:
		ref += [i+j for j in ref]
	print min(abs(sum(a)-2*i) for i in ref)

Submission status: Accepted

Solution code:
# AOJ 1045: Split Up!
# Python3 2018.7.6 bal4u

while True:
	n = int(input())
	if n == 0: break
	t = list(map(int, input().split()))
	s = sum(t)
	ans = s >> 1
	if ans in t:
		print(s - 2*ans)
		continue
	a = [v for v in t if v < ans]
	S, f, Q, qlen = set(), True, [0], 1
	for v in a:
		i, k = 0, qlen
		while k:
			v2 = v + Q[i]
			k, i = k-1, i+1
			if v2 == ans:
				f = False
				break
			if v2 < ans and v2 not in S:
				S.add(v2)
				Q.append(v2)
				qlen += 1
	if f:
		while True:
			ans -= 1
			if ans == 0: break
			if ans in S: break;
	print(s - 2*ans)

Submission status: Accepted

Solution code:
A = 0
def solve(l,c,sa,sb):
    if 2*sa>=A: return 2*sa-A
    if 2*sb>=A: return 2*sb-A
    return min(solve(l,c+1,sa+l[c],sb),solve(l,c+1,sa,sb+l[c]))
while 1:
    n = input()
    if n==0: break
    a = map(int, raw_input().split())
    ans = 10**7; A = sum(a);
    print solve(a,0,0,0)

Submission status: Accepted

Solution code:
A = 0
def solve(l,c,sa,sb):
    if 2*sa>=A: return 2*sa-A
    if 2*sb>=A: return 2*sb-A
    return min(solve(l,c+1,sa+l[c],sb),solve(l,c+1,sa,sb+l[c]))
while 1:
    n = input()
    if n==0: break
    a = map(int, raw_input().split())
    ans = 10**7; A = sum(a);
    print solve(a,1,a[0],0)

Submission status: Accepted

Solution code:
import itertools
while 1:
	n = input()
	if n == 0: break
	a = map(int,raw_input().split())
	all = sum(a)
	ans = all
	for i in range((n+1)/2+1):
		for party in itertools.combinations(a,i):
			ans = min(ans,abs(all-2*sum(party)))
	print ans

Submission status: Accepted

Solution code:
def solve(a,i,sa,sb):
	if 2*sa >= all: return 2*sa-all
	if 2*sb >= all: return 2*sb-all
	return min(solve(a,i+1,sa+a[i],sb),solve(a,i+1,sa,sb+a[i]))
	
while 1:
	n = input()
	if n == 0: break
	a = sorted(map(int,raw_input().split()))
	all = sum(a)
	print solve(a,1,a[0],0)

Submission status: Accepted

Solution code:
def solve(a,i,sa,sb):
	if 2*sa >= all: return 2*sa-all
	if 2*sb >= all: return 2*sb-all
	return min(solve(a,i+1,sa+a[i],sb),solve(a,i+1,sa,sb+a[i]))
	
while 1:
	n = input()
	if n == 0: break
	a = sorted(map(int,raw_input().split()))[::-1]
	all = sum(a)
	print solve(a,1,a[0],0)

Submission status: Accepted

Solution code:
while 1:
	n = input()
	if n == 0: break
	a = map(int,raw_input().split())
	s = sum(a)
	ref = [0]
	for i in a:
		ref += [i+j for j in ref if j < s/2]
	print min(abs(s-2*i) for i in ref)

Submission status: Accepted

Solution code:
while 1:
	n = input()
	if n == 0: break
	a = sorted(map(int,raw_input().split()))[::-1]
	s = sum(a)
	L = [0]
	for i in a:
		L += [i+j for j in L if j < s/2]
	print min(abs(s-2*i) for i in L)

Submission status: Accepted

Solution code:
def S(a,i,x,y):
	if 2*x >= A: return 2*x-A
	if 2*y >= A: return 2*y-A
	return min(S(a,i+1,x+a[i],y),S(a,i+1,x,y+a[i]))
while 1:
	n = input()
	if n == 0: break
	a = sorted(map(int,raw_input().split()))[::-1]
	A = sum(a)
	print S(a,1,a[0],0)

Submission status: Accepted

Solution code:
def S(i,x,y):
	w = max(x,y)
	return 2*w-A if 2*w >= A else min(S(i+1,x+a[i],y),S(i+1,x,y+a[i]))
while 1:
	n = input()
	if n == 0: break
	a = sorted(map(int,raw_input().split()))[::-1]
	A = sum(a)
	print S(1,a[0],0)

Submission status: Accepted

Solution code:
def S(i,x,y):
	d=2*max(x,y)-sum(a)
	return d if d>=0 else min(S(i+1,x+a[i],y),S(i+1,x,y+a[i]))
while 1:
	if input()==0:break
	a=sorted(map(int,raw_input().split()))[::-1]
	print S(1,a[0],0)

Submission status: Accepted

Solution code:
def S(i,x,y):
	if 2*x >= A: return 2*x-A
	if 2*y >= A: return 2*y-A
	return min(S(i+1,x+a[i],y),S(i+1,x,y+a[i]))
while 1:
	n = input()
	if n == 0: break
	a = sorted(map(int,raw_input().split()))[::-1]
	A = sum(a)
	print S(1,a[0],0)

Submission status: Accepted

Solution code:
while True:
    n = int(input())
    if n == 0:
        break
    a = list(map(int, input().split()))
    b = sum(a)
    ans =  b >> 1
    if ans in a:
        print(b - 2*ans)
        continue
    c = [v for v in a if v < ans]
    s , f, q, qlen = set(), True, [0], 1
    for v in c:
        i, k = 0, qlen
        while k:
            v2 = v + q[i]
            k, i = k-1, i+1
            if v2 == ans:
                f = False
                break
            if v2 < ans and v2 not in s:
                s.add(v2)
                q.append(v2)
                qlen += 1
                
    if f:
        while True:
            ans -= 1
            if ans == 0:
                break
            if ans in s:
                break
    print(b - 2 * ans)

Submission status: Accepted

Solution code:
def main():
  while True:
    n = int(input())
    if n == 0:
      break
    alst = list(map(int, input().split()))
    s = sum(alst)
    alst = [a * 2 for a in alst]
    lst = [-s]
    for a in alst:
      lst.extend([i + a for i in lst])
    print(min(map(abs, lst)))
main()

Submission status: Runtime Error

Solution code:
import itertools
while 1:
	n = input()
	if n == 0: break
	s = sorted(map(int,raw_input().split()))
	sm = sum(s)
	for i in range(1,n-1):
		ans = sorted(abs(sm - 2*sum(party)) for party in itertools.combinations(s,i))[0]
		if ans == 0: break
	print ans

Submission status: Runtime Error

Solution code:
import itertools
while 1:
	n = input()
	if n == 0: break
	a = sorted(map(int,raw_input().split()))
	all = sum(a)
	ans = all
	for i in range((n+1)/2+1):
		c = 0
		for party in itertools.combinations(a,i):
			d = all-2*sum(party)
			if c == 0 and d < -ans
				break
			ans = min(ans,abs(d))
			c = 1
	print ans

Submission status: Runtime Error

Solution code:
while 1:
	n = input()
	if n == 0: break
	a = map(int,raw_input().split())
	ref = [0]
	for i in a:
		ref += [i+j for j in ref if j < ans/2]
	print min(abs(sum(a)-2*i) for i in ref)

Submission status: Runtime Error

Solution code:
def S(i,x,y):
	for w in [x,y]
		if 2*w >= A: return 2*w-A
	return min(S(i+1,x+a[i],y),S(i+1,x,y+a[i]))
while 1:
	n = input()
	if n == 0: break
	a = sorted(map(int,raw_input().split()))[::-1]
	A = sum(a)
	print S(1,a[0],0)