No.545 ママの大事な二人の子供

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 65
作問者 : horiesinitihoriesiniti / テスター : 37zigen37zigen

3 ProblemId : 1203 / 出題時の順位表

問題文

ママには二人の大事な子供AとBがいます。 ママは二人を平等に愛しており、二人を分け隔てなく育てています。 ママは今n個の品物を持っており、n個全てを2人に分配しようとしています。 しかし二人は、品物をもらったとき、品物に対する満足度が違います。 Aがあんパンをもらえば、Aの満足度は15でBがもらえばBの満足度は30だという具合です。 ママは二人とも大好きなので、Aの満足度合計とBの満足度合計の差異が最小になるように品物を分配することにしました。 データから差異の最小値(つまり差の絶対値)を求めるプログラムを書いてください。 データは以下の通り。

品物の数n。
つづくn行に品物に対する二人の満足度AiとBiが与えられます。
A1ならAが品物1をもらったときの満足度。B1なら品物1をBがもらったときの満足度。
AiならAが品物iをもらったときの、BiならBが品物iをもらったときの満足度という具合です。

入力

$n$
$A_1$ $B_1$
$A_2$ $B_2$
$\dots$
$A_{n}$ $B_{n}$

$1 \leq n \leq 32$
$0 \leq Ai \leq5000000000$
$0 \leq Bi \leq5000000000$
Ai,品物iをAがもらったときのAの満足度、Biは品物iをBがもらったときのBの満足度です。 2人とも品物をもらったときの満足度を単純合計し、満足度の差異が最小になるように分配されたときの満足度合計差異を計算してください。


出力

2人の満足度差異絶対値の最小値を出力してください。

サンプル

サンプル1
入力
1
10 15
出力
10

品物が一個しかなくBに分けるよりはAに分けるほうが満足度の差異が少ない。 母は満足度の最高値を目指しているのではなく、分配に置ける差異を最少化したいのだ。 全部の品物をAとBに配るという条件なので配らないという選択肢はない。 全部の品物がAかBどちらかだけに配られるケースもあり得る。

サンプル2
入力
3
25 14
25 23
32 10
出力
1

品物1と3をBに品物2をAに分配すれば差分が最小化される。

提出ページヘ