Problem:


Score : 700 points

Problem Statement

You are given N integers A_1, A_2, ..., A_N.

Consider the sums of all non-empty subsequences of A. There are 2^N - 1 such sums, an odd number.

Let the list of these sums in non-decreasing order be S_1, S_2, ..., S_{2^N - 1}.

Find the median of this list, S_{2^{N-1}}.

Constraints

1 \leq N \leq 2000

1 \leq A_i \leq 2000

All input values are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the median of the sorted list of the sums of all non-empty subsequences of A.

Sample Input 1

3
1 2 1

Sample Output 1

2

In this case, S = (1, 1, 2, 2, 3, 3, 4). Its median is S_4 = 2.

Sample Input 2

1
58

Sample Output 2

58

In this case, S = (58).



Sample input:
3
1 2 1


Sample output:
2

Submission status: Runtime Error

Solution code:

n=int(input())
arr=[int(x) for x in input().split()]
sum = sum(arr) 
ans=[]
      
    # dp[i][j] would be true if arr[0..i-1]  
    # has a subset with Sum equal to j.  
dp = [[False for i in range(Sum + 1)] for i in range(n + 1)]

                   
    # There is always a subset with 0 Sum  
for i in range(n + 1):
  dp[i][0] = True
  
    # Fill dp[][] in bottom up manner  
  for i in range(1, n + 1): 
    dp[i][arr[i - 1]] = True
    for j in range(1, Sum + 1): 
      if (dp[i - 1][j] == True): 
        dp[i][j] = True
        dp[i][j + arr[i - 1]] = True
              
    # Print last row elements  
for j in range(Sum + 1):
  if (dp[n][j] == True):
    ans.append(j)
if(n%2==0):
  print((ans[(n//2)-1] + ans[n//2])/2.0)
else:
  print(ans[n//2])

Submission status: Runtime Error

Solution code:
n=int(input())
a=[int(x) for x in input().split()]
b=[[]]
for i in a:
  b+=[[i]+j for j in b]
 c=sorted(b)
c=c[1:]
d=[]
for i in c:
  d.append(sum(i))
d=sorted(d)
k=len(d)
if(k%2==0):
  print((d[(k//2)-1] + d[k//2])/2.0)
else:
  print(d[k//2])

Submission status: Runtime Error

Solution code:
import io, os
from sys import stdin, stdout
from typing import List
class Solution():
    def __init__(self):
        return 
    def getMedian(self, ar:List[int]):
        n = len(ar)
        if n==1: 
            return ar[0]
        arsum = sum(ar)
        f = [0]*(arsum+1)
        f[0]=1
        for i in range(n):
            for j in range(arsum, ar[i]-1, -1):
                f[j]+=f[j-ar[i]]
        expect = pow(2, (n-1))
        accu = 0
        #search for median
        for i in range(1, arsum+1):
            accu += f[i]
            if accu>=expect:
                return i


if __name__ == "__main__":
    # fto =os.path.join( os.getcwd(), "AT3857.01.inp")
    # stdin = open(fto)
    n = int(stdin.readline())
    ar = [int(x) for x in stdin.readline().split()]
    sol = Solution()
    print(str(sol.getMedian(ar)))
    # stdout.write(str(n))

Submission status: Runtime Error

Solution code:
N = int(input())
a = sorted(list(map(int, input().split())))
if len(a)==1: print(a[0]); exit()
median = a[N//2+1]
print(sum(a)-median)

Submission status: Runtime Error

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

tgt = sum(a)//2
dp = [[0]*(tgt+1) for _ in range(n+1)]
for i in range(n):
    for w in range(min(a[i],tgt+1)):
        dp[i+1][w] = dp[i][w]
    for w in range(a[i],tgt+1):
        dp[i+1][w] = dp[i][w-a[i]] + a[i]
print(sum(a)-dp[-1][-1])

Submission status: Runtime Error

Solution code:
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <cmath>
#include <ctime>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <bitset>
using namespace std;
typedef long long LL;
LL gi () {
    LL ret=0; char ch=getchar();
    while((ch<'0' || ch>'9') && ch!='-') ch=getchar();
    char c=ch=='-'?getchar():ch;
    while(c>='0' && c<='9') ret=ret*10+c-'0',c=getchar();
    return ch=='-'?-ret:ret;
}
const int N = 1000 + 10;
int n,a[N],S;
bitset<N*N> dp;
int main () {
    n = gi();
    for(int i=1;i<=n;i+=1) a[i] = gi(), S += a[i];
    dp[0] = 1;
    for(int i=1;i<=n;i+=1) {
        dp |= (dp<<a[i]);
    }
    for(int i=S/2;i<=S;i+=1)
        if(dp[i]) {
            printf("%d",i); exit(0);
        }
    return 0;
}

Submission status: Runtime Error

Solution code:
from itertools import combinations

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

if N % 2 == 1:
    num = int(N / 2) + 1
    print(sum(A[:num]))
else:
    comb = list(combinations(A, int(N / 2)))
    SUM = [sum(c) for c in comb]
    SUM.sort()
    print(SUM[2 ** (N - 1)])

Submission status: Runtime Error

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

if N % 2 == 1:
    num = int(N / 2) + 1
    print(sum(A[:num]))
else:
    print(sum(A[:N / 4]) + sum(A[N * 3 / 4:]))

Submission status: Runtime Error

Solution code:
def solve():
    n = int(input())
    A = list(map(int, input().split(" ")))
    sum_list = []
    for i in range(1, n + 1):
        for ele in list(itertools.combinations(A, i)):
            sum_list.append(sum(ele))

    sum_list.sort()
    length = len(sum_list)
    print(sum_list[length // 2])

solve()

Submission status: Runtime Error

Solution code:
from statistics import median


def solve():
    n = int(input())
    A = list(map(int, input().split(" ")))
    sum_list = []
    for i in range(1, n + 1):
        for ele in list(itertools.combinations(A, i)):
            sum_list.append(sum(ele))

    sum_list.sort()
    print(median(sum_list))


solve()

Submission status: Runtime Error

Solution code:
import itertools
n = int(input())
a = list(map(int, input().split()))
a.sort()
#部分列の和を0番目から数えたk番目の要素がtarget
target = (2**n - 1) // 2
counter = 0
for i in range(1, n + 1):
    if len(list(itertools.combinations(a, i))) - 1 <= target - counter:
        print(sum(list(itertools.combinations(a, i))[target - counter - 1]))
        break
    else:
        counter += len(list(itertools.combinations(a, i)))

Submission status: Runtime Error

Solution code:
n=int(input())
a=[]
sa=input().split(' ')
s=0
for i in sa:
    t=int(i)
    a.append(t)
    s+=t
dp=[0]*(s+1)
dp[0]=1
for i in a:
    for j in range(s,i-1,-1):
        dp[j]+=dp[j-i]
tg=(2**n)/2
t=0
for i in range(s+1):
    t+=dp[i]
    if t>tg:
        break
print(i)