以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。


可复制的 PDF 提取文本
2 お菓子の分割
問題
長さN ミリメートルの棒状のお菓子が1 本ある(ここでN は偶数).2 人のJOI
関係者が,このお菓子を複数本に切断して,合計N ミリメートルずつに分けること
2
にした.
理由は不明であるが,このお菓子は場所によって切断のしやすさが異なっている.
2 人は,お菓子を左から1 ミリメートルごとに調べ,各場所で切断に何秒かかるか
を割り出した.2 人がお菓子を分けるための切断にかかる秒数の最小値を求めるプ
ログラムを作成せよ.
入力
入力ファイルのファイル名はinput.txt である.
入力の1 行目には,棒の長さN(2 ≦N ≦10000 ,ただしN は偶数) が書かれてい
る.入力のi + 1 行目(1 ≦i ≦N −1) には,左端からi ミリメートル目の場所の切
断にかかる秒数を表す整数ti (1 ≦ti ≦10000) が書かれている.切断可能な場所が
N −1 箇所であることに注意せよ.
採点用データのうち,配点の5% 分については,高々2 カ所を切断することで最
小値を実現でき,10% 分については,高々3 カ所を切断することで最小値を実現で
きる.配点の20% 分については,N ≦20 である.
出力
出力ファイルのファイル名はoutput.txt である.
2 人がお菓子を分るための切断にかかる秒数の最小値を含む1 行からなる.
問題2-1
入出力の例
input.txt
6
1
8
12
6
2
output.txt
7
この場合,左端から1 ミリメートルと4 ミリメートルの場所で切断するとかかる
秒数が最小となる.かかる秒数は1 秒と6 秒で,合計7 秒である.
問題2-2