C - Snack Distribution Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君と青木君は兄弟です。お母さんが N 個のお菓子を買ってきたので、二人で分けることにしました。お菓子には 1 から N までの番号が付いており、i 番目 (1 \leq i \leq N) のお菓子の美味しさは A_i です。

二人は以下のルールでお菓子を分けます。

  • 各お菓子は丸ごと、高橋君か青木君のちょうど一方に渡す。どちらにも渡さないお菓子があってはならない。
  • 高橋君と青木君はそれぞれ 1 個以上のお菓子を受け取る。

上記のルールを満たすすべての分け方のうち、高橋君が受け取るお菓子の美味しさの合計と青木君が受け取るお菓子の美味しさの合計の差の絶対値が最小となる値を求めてください。

制約

  • 2 \leq N \leq 200
  • 1 \leq A_i \leq 1000 \quad (1 \leq i \leq N)
  • 入力はすべて整数である。

入力

N
A_1 A_2 \ldots A_N
  • 1 行目には、お菓子の個数を表す整数 N が与えられる。
  • 2 行目には、各お菓子の美味しさを表す整数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。

出力

高橋君が受け取るお菓子の美味しさの合計と青木君が受け取るお菓子の美味しさの合計の差の絶対値の最小値を 1 行で出力せよ。

入力例 1

3
3 1 4

出力例 1

0

入力例 2

5
8 3 7 2 10

出力例 2

0

入力例 3

15
12 7 25 18 3 30 11 5 16 9 22 14 6 27 20

出力例 3

1

入力例 4

60
137 42 256 19 384 73 512 91 628 105 749 118 860 134 975 150 231 467 589 703 816 929 34 65 98 123 177 212 299 345 401 456 500 555 600 654 701 742 789 830 876 920 963 1000 15 28 39 57 84 111 166 222 333 444 666 777 888 999 250 750

出力例 4

1

入力例 5

2
1 1000

出力例 5

999

Score : 366 pts

Problem Statement

Takahashi and Aoki are brothers. Their mother bought N snacks, and they decided to divide them between the two of them. The snacks are numbered from 1 to N, and the deliciousness of the i-th (1 \leq i \leq N) snack is A_i.

They divide the snacks according to the following rules:

  • Each snack must be given wholly to exactly one of Takahashi or Aoki. There must be no snack that is given to neither of them.
  • Takahashi and Aoki each receive at least 1 snack.

Among all ways of dividing the snacks that satisfy the above rules, find the minimum possible absolute difference between the total deliciousness of the snacks Takahashi receives and the total deliciousness of the snacks Aoki receives.

Constraints

  • 2 \leq N \leq 200
  • 1 \leq A_i \leq 1000 \quad (1 \leq i \leq N)
  • All inputs are integers.

Input

N
A_1 A_2 \ldots A_N
  • The first line contains an integer N representing the number of snacks.
  • The second line contains integers A_1, A_2, \ldots, A_N representing the deliciousness of each snack, separated by spaces.

Output

Print in one line the minimum absolute difference between the total deliciousness of the snacks Takahashi receives and the total deliciousness of the snacks Aoki receives.

Sample Input 1

3
3 1 4

Sample Output 1

0

Sample Input 2

5
8 3 7 2 10

Sample Output 2

0

Sample Input 3

15
12 7 25 18 3 30 11 5 16 9 22 14 6 27 20

Sample Output 3

1

Sample Input 4

60
137 42 256 19 384 73 512 91 628 105 749 118 860 134 975 150 231 467 589 703 816 929 34 65 98 123 177 212 299 345 401 456 500 555 600 654 701 742 789 830 876 920 963 1000 15 28 39 57 84 111 166 222 333 444 666 777 888 999 250 750

Sample Output 4

1

Sample Input 5

2
1 1000

Sample Output 5

999