第17回日本情報オリンピック　予選４

2017年12月11日
情報オリンピック日本委員会

問題文

水ようかんとは，おもに小豆からなる餡を型に流し込んで寒天で固めることにより作られる和菓子である．いま，JOI 君の手元には，横長の直方体の形をした水ようかんがひとつある．JOI 君は，今日のおやつとしてこの水ようかんを食べる予定である．

この水ようかんには，縦方向の切れ目が全部で N-1 箇所に入っている．水ようかんの長さは L_1 + L_2 + ... + L_N であり，i 番目 (1 ≦ i ≦ N-1) の切れ目は，左から L_1 + L_2 + ... + L_i の位置にある．

この水ようかんは丸ごと食べるには大きすぎるので，JOI 君は，水ようかんに入っている切れ目から 1 箇所以上を選び，選んだ切れ目に沿って水ようかんを切って，複数のピースに切り分けることにした．ただし，ピースの大きさが不揃いでは見栄えが悪いので，長さ最大のピースと最小のピースの長さの差ができるだけ小さくなるように切ることにした．

長さ最大のピースと最小のピースの長さの差の最小値を求めよ．

制約

• 2 ≦ N ≦ 50
• 1 ≦ L_i ≦ 1000 (1 ≦ i ≦ N)

入力・出力

入力
入力は以下の形式で標準入力から与えられる．
N
L_1
L_2
:
L_N

出力
長さ最大のピースと最小のピースの長さの差の最小値を 1 行で出力せよ．

小課題

小課題 1 [10点]

• N ≦ 15

小課題 2 [27点]

• L_i ≦ 10 (1 ≦ i ≦ N)

小課題 3 [63点]

• 追加の制限はない．

入出力例

入力例 1
11
2
3
8
4
7
6
6
5
1
7
5

出力例 1
2

この例では，4 番目および 7 番目の切れ目に沿って切り分けることで，長さ 17, 19, 18 の 3 つのピースに切り分けることができる． このとき，いちばん長いピースは長さ 19 で，いちばん短いピースは長さ 17 であるので，長さの差は 2 となる． これが最小値なので，2 を出力する．

入力例 2
2
1
10

出力例 2
9

どんなに大きさが不揃いであっても，必ず 1 箇所以上を切る必要がある．

入力例 3
5
5
5
5
5
5

出力例 3
0

この例では水ようかんをちょうど同じ大きさの 5 つのピースに分割できる．