問題
IOI2015の開会式の最後のショーが行われている．開会式の間に，各チームは，主催者からのお土産の入った1つの箱を受け取ることになっていた．しかし，スタッフはみ開会式に魅了されていたため，お土産のことをすっかり忘れてしまっていた．お土産のことを覚えていた唯一のスタッフはAmanである．彼は熱意にあふれたスタッフで，IOIを完璧ものとしたかったため，すべてのお土産を各チームに最小の時間で渡したいと思っている．
開会式会場は，L 個の同等の区画に区切られた円状の形をしている．各区画には 0 から L - 1 までの連続した番号がつけられている．すなわち，各 0 ≦ i ≦ L - 2 に対して，区画 i は区画 i + 1 と隣接しており，また区画 L - 1 は区画 0 と隣接している．開会式会場には N チームがおり，それぞれのチームは 1 つの区画にいる．各区画にはいくらでも多くのチームがいるかもしれないし，いくつかの区画にはどのチームもいないかもしれない．
同じお土産が N 個ある．最初，Amanとすべてのお土産は区画 0 にある．Amanはすべてのチームに 1 つずつのお土産を渡し，その後区画 0 に戻ってこなければならない．いくつかのチームは区画 0 にいるかもしれないことに注意せよ．
Amanは一度に最大で K 個までのお土産を持つことができる．Amanは区画 0 からお土産を持ち出す．お土産を持ち出す行動には時間はかからない．すべてのお土産は，いずれかのチームのもとへ届くまで運ばれければならない．Amanが 1 個以上のお土産を持っており，お土産をまだ受け取っていないチームのいる区画にいるときには，彼が持っているお土産のつをそのチームに渡すことができる．この行動には時間はかからない．時間のかかる唯一の行動は移動である．Amanは円状の会場を両方向に移動することができる．Amanが時計回り，あるいは反時計回りに隣接した区画へ移動するためには，彼が持っているお土産の量に関わらず 1 秒がかかる．
あなたの課題は，Amanがすべてのお土産を各チームに渡し，その後区画まで戻ってくるために，最小で何秒かかるかを求めることである．
例 (Example)
この例では，N = 3 チームが存在し，Amanが一度に運ぶことのできるお土産の数は最大で K = 2 であり，開会式会場の区画の数は L = 8 である．また，各チームはそれぞれ区画 1, 2, 5 にいる．
所要時間を最小にする方法の 1 つは，上の図に示されている．
最初，Amanは 2 つのお土産を持ち出し，1 つのお土産を区画 2 にいるチームに届け，その後区画 5 にいるチームにもう 1 つのお土産を届けた後，区画 0 に戻ってくる．この一連の移動には 8 秒かかる．次に，Amanは残りの 1 つのお土産を持ち出し，それを区画 1 にいるチームに届け，区画 0 に戻ってくる．この移動は 2 秒かかる．よって，移動時間は合計で 10 秒になる．
課題 (Task)
N, K, L および，すべてのチームにいる区画の番号が与えられる．
Amanがすべてのお土産を各チームに届け，その後区画 0 まで戻ってくるためにかかる時間の最小値を求めるプログラムを作成せよ．
あなたは以下に示す関数deliveryを実装する必要がある．
- delivery(N, K, L, positions) — この関数は，採点用プログラムによってちょうど 1 回だけ呼び出される．
- N:チームの数である．
- K:Amanが同時に持てるお土産の数の最大数である．
- L:開会式会場にある区画の数である．
- positions:長さ N の配列である．positions[0],...,positions[N-1]は，それぞれのチームがいる区画の番号を表す．positionsの要素は，減少しない順番で並んでいる．
- この関数は，Amanがすべてのお土産を各チームに渡し，その後区画まで戻ってくるためにかかる秒数の最小値を返さなければならない．
小課題 (Subtasks)
| 小課題 | 得点 | N | K | L |
|---|---|---|---|---|
| 1 | 10 | 1 ≦ N ≦ 1,000 | K = 1 | 1 ≦ L ≦ 109 |
| 2 | 10 | 1 ≦ N ≦ 1,000 | K = N | 1 ≦ L ≦ 109 |
| 3 | 15 | 1 ≦ N ≦ 10 | 1 ≦ K ≦ N | 1 ≦ L ≦ 109 |
| 4 | 15 | 1 ≦ N ≦ 1,000 | 1 ≦ K ≦ N | 1 ≦ L ≦ 109 |
| 5 | 20 | 1 ≦ N ≦ 106 | 1 ≦ K ≦ 3,000 | 1 ≦ L ≦ 109 |
| 6 | 30 | 1 ≦ N ≦ 107 | 1 ≦ K ≦ N | 1 ≦ L ≦ 109 |
採点プログラムのサンプル (Sample grader)
採点プログラムのサンプルは，以下のフォーマットで入力を読み込む:
- 1行目: N K L
- 2行目: positions[0] ... positions[N - 1]
実行時に必要なファイル
boxes.zip- boxes.h
- grader.cpp grader.c
- boxes.cpp boxes.c
- sample.in sample.out
ヘッダファイル
採点用プログラムのサンプル
実装ファイル(解答はここに実装)
サンプル入出力ファイル
コンパイルの方法
C++
g++ grader.cpp boxes.cpp
C
gcc grader.c boxes.c