Informatica Online Judge

  합의 중간값 [2174 / 087E]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 8   Total Tried : 8


The Champion of this Problem (C++) : icp1481 - 72ms / 257byte
My Best Submission (C++) : N/A

[AtCoder(tourist)]

Background

$N$개의 정수로 이루어진 수열 $A_1$, $A_2$, ... , $A_N$이 있다.

$A$의 부분집합들 중 공집합을 제외한 모든 부분집합들의 합을 구하면 $2^N-1$개가 존재한다.

부분집합들의 합은 항상 홀수개임이 명백하다. 이들 합을 비내림차순으로 정렬한 결과를 $S_1$, $S_2$, ... ,$S_{2^N-1}$이라고 하자.

이 정렬된 값들 중 중간값인 $S_{2^{N-1} }$의 값을 구하시오.

Input

입력 형식은 다음과 같다.

$N$
$A_1$ $A_2$ … $A_N$

[입력값의 정의역]
$1≤N≤2000$
$1≤A_i≤2000$
입력되는 모든 값은 정수이다.

Output

공집합을 제외한 부분집합들의 합의 중간값을 출력한다.

IO Example

입력
3
1 2 1

출력
2

* 설명 : 각 부분집합들의 합은 1,1,2,2,3,3,4 가 되므로 중간값은 2이다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]