100 atcoder#ABC074B. [ABC074B] Collecting Balls (Easy Version)
[ABC074B] Collecting Balls (Easy Version)
配点: 点
問題文
平面上に 個のボールがあります。このうち 番目のボールの位置は です。 したがって、 本の直線 , , , の上にそれぞれ 個ずつボールがあることになります。
すぬけ君は、これらのボールを回収するために、タイプ A, B のロボットを 台ずつ用意しました。 さらに、タイプ A のロボットのうち 台目のものを位置 に、タイプ B のロボットのうち 台目のものを位置 に設置しました。 したがって、 本の直線 , , , の上にそれぞれ 台のタイプ A のロボットと、 台のタイプ B のロボットが設置されたことになります。
それぞれのタイプのロボットは起動されると以下のように動作します。
- タイプ A のロボットは、位置 で起動されると、直線 上にあるボールの位置まで移動し、ボールを回収してもとの位置 に戻って停止する。そのようなボールが存在しない場合は何もせずに停止する。
- タイプ B のロボットは、位置 で起動されると、直線 上にあるボールの位置まで移動し、ボールを回収してもとの位置 に戻って停止する。そのようなボールが存在しない場合は何もせずに停止する。
これら 台のロボットのうちいくつかを起動してボールをすべて回収するとき、ロボットの移動距離の総和として考えられる値のうち最小のものを求めてください。
制約
- 入力値はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
出力
ロボットの移動距離の総和として考えられる値のうち最小のものを出力せよ。
1
10
2
4
ボールが 個だけあり、タイプ A および B のロボットが つずつあります。
タイプ A のロボットを用いてボールを回収すると、ボールの位置までの移動距離は であり、もとの位置に戻るための移動距離も であるので、合計の移動距離は となります。
同様にタイプ B のロボットを用いてボールを回収したときの移動距離の合計を計算すると となります。
よって、タイプ A のロボットを用いて回収すると合計の移動距離が最小となり、そのときの移動距離である を出力します。
2
9
3 6
12
つめのボールはタイプ A のロボットで、 つめのボールはタイプ B のロボットで回収すると移動距離が最小となります。
5
20
11 12 9 17 12
74