問題一覧 > 通常問題

No.2918 Divide Applicants Fairly

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 18
作問者 : ゆにたりー卿 / テスター : 👑 みうね 👑 binap
お気に入りにしたユーザー ProblemId : 11358 / 自分の提出
問題文最終更新日: 2024-11-08 11:33:49
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original

Problem Statement

Iwai Seijin recruited participants for a competitive programming contest he is organizing, and $N$ people applied. The rating of the $i$-th applicant is $R_i$.

The contest is a team competition, and Iwai Seijin will now divide the applicants into teams as follows.

  • Pick any number of applicants of his choice, find fault with them, and prevent them from participating in the contest.
  • Assign each applicant he did not find fault with to exactly one of the red team and the blue team.
Here, each team must have at least $1$ member, and the number of members of the red team and the number of members of the blue team must be equal.

For each division into teams, the strength of a team is defined as the sum of the ratings of the members belonging to that team.
To make the contest exciting, Iwai Seijin wants the strengths of the two teams to be as close as possible. Find the minimum possible absolute difference between the strength of the red team and the strength of the blue team when Iwai Seijin divides the teams optimally.

Input

$N$
$R_1\ R_2\ \dots\ R_N$
  • $2 \leq N \leq 40$
  • $0 \leq R_i \leq 8 \times 10 ^ 5$
  • All inputs are integers.

Output

Output the minimum possible absolute difference between the strengths of the two teams as an integer.
Print a newline at the end.

Sample

Sample 1
Input
4
1050 1100 1300 1370
Output
20

If the 1st and 4th applicants are assigned to the red team and the 2nd and 3rd applicants are assigned to the blue team, the strength of the red team is $1050 + 1370 = 2420$ and the strength of the blue team is $1100 + 1300 = 2400$, so the absolute difference between the strengths of the two teams is $|2420 - 2400| = 20$. No division into teams makes this absolute difference any smaller.

Sample 2
Input
6
0 1 2 4 8 16
Output
1

If he finds fault with all applicants other than the 1st and 2nd applicants so that they do not participate, and assigns the 1st applicant to the red team and the 2nd applicant to the blue team, the absolute difference between the strengths of the two teams is $|0 - 1| = 1$. No division into teams makes this absolute difference any smaller.

Sample 3
Input
5
1694 491 835 1875 1343
Output
7

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。