分数: 700 点
问题陈述
你被给予 N 整数 A_1, A_2, ..., A_N.
考虑所有非空子序列的总和 A。有 2^N - 1 这样的总和,是一个奇数。
令这些总和按非降序排列的列表为 S_1, S_2, ..., S_{2^N - 1}.
找到这个列表的中位数, S_{2^{N-1}}.
约束
- 1 \leq N \leq 2000
- 1 \leq A_i \leq 2000
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 ... A_N
输出
打印所有非空子序列之和的排序列表的中位数 A.
示例输入 1
3 1 2 1
示例输出 1
2
在这种情况下, S = (1, 1, 2, 2, 3, 3, 4)。其中位数为 S_4 = 2.
示例输入 2
1 58
示例输出 2
58
在这种情况下, S = (58).