TopCoder

Thumb hsnu2016
Adrien Wu
烏梭聯合王國,簡稱烏梭,為北佤羅善、安那海及佤羅善島弧國家之一。

User's AC Ratio

97.1% (34/35)

Submission's AC Ratio

37.4% (158/422)

Tags

Description

一次偶然的機會,小向來到了拔克薩斯(Boxes)城。這個消息不知為何走漏了,於是來自全世界各地的N個人也來到了拔克薩斯城,分散在城裡的不同房間,為了要一睹小向的風采,或者可以看到稀有的「轉?皮」現象發生。你可能有個疑問:為甚麼是「房間」?這得從拔克薩斯城的構造談起。

拔克薩斯城的構造極度特別──它實際上是一個大型的環狀建築物。這個建築物裡面總共有L個房間,編號為0到L-1,編號x的房間與編號x+1的房間相通。由於它環狀的結構,編號0的房間與編號L-1的房間也是相通的。

在編號0的房間中有一個神祕的裝置。外行人常常稱它為「黑魔法能量儲存裝置」,又或者「?皮驅動器」,然而實際上,它的名稱是「רִʃעכשל」(翻譯出來也許是PBDS吧),被刻在其上。

由於受到廣大群眾的鼓舞,小向要把她「轉?皮」的神技展示給到訪的每一個人看。然而,由於轉?皮是非常耗能的,小向在接受רִʃעכשל的充能之後,最多只能轉?皮給K個人看,就必須回到0號房再次充能,避免發生?皮轉不動的慘劇。

拔克薩斯城非常的大,所以要花很久的時間才能從一個房間到另一個房間;唯有搭乘非常昂貴的拔克薩斯鐵路,才能快速穿梭於其中。拔克薩斯鐵路最大的特色是不需要等待,每一個房間內都有待命的車,上車之後就會依照你指定的方向以每秒1個房間的速度駛向目標車站。拔克薩斯鐵路的計費方式再正常不過了:如果搭乘鐵路從第x個房間到第y個房間,不論是往哪一個方向行駛,費用都是 $ \left[ 2 \sqrt{\pi} (\frac{x^ 3}{y+1}+\frac{y^ 3}{x+1}) \right] $ 拔克薩斯幣([z]代表不大於z的最大整數)。

多次獲得魔奧(IMO,International Magic Olympiad)獎牌的小向是個有錢人,她才不在乎要花多少錢,然而每秒1個房間的速度實在是太慢了。她想要在最短的時間內完成轉?皮給在城內的全部N個人看。小向對四則運算非常不在行,尤其是加法和減法,所以她把任務交給你──天龍國立拔克薩斯大學魔法工程系的高才生,希望你可以幫她計算出她從0號房間出發,最短可以在多少秒內轉?皮給全部N個人看,再回到0號房。

備註:由於小向對於轉?皮相關的事情都非常熟悉,她可以在1普朗克時間內轉完?皮,也可以透過רִʃעכשל在1普朗克時間內充好能。為了你的計算方便以及讓結果好看一點,你還是忽略這些時間比較好。要注意的是,有些人和小向交情甚篤,所以0號房裡面也有可能有圍觀群眾。由於受到小向的電場影響,拔克薩斯城內的圍觀群眾在小向還沒有表演完畢前,是不能移動的。

Input Format

第一行有一個整數T,代表有幾筆測資。
每一筆測資占兩行。第一行有三個整數,依序為N、K、L;第二行有N個整數,代表每個人等待的位置編號。第二行的數字們已經以非遞減順序排好序。

對於10%的測資,N<=1000,K=1。
對於10%的測資,N<=1000,K=N。
對於15%的測資,N<=10。
對於15%的測資,N<=1000。
對於20%的測資,N<=106 ,K<=3000。
對於所有的測資,1<=N<=107 ,1<=K<=N,1<=L<=109

Output Format

對每筆測資輸出一行,包含一個數字,代表完成整個表演過程的秒數。

Sample Input

1
3 2 8
1 2 5

Sample Output

10

Hints

如果你覺得你被小向的電場影響而做不出題目,你可以嘗試看看這裡:http://olympiads.kz/ioi2015/day1/boxes/th-TH.THA.pdf

Problem Source

IOI 2015 Day 1
Problem set by 果茶
Description by Yihda Yol

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 15
For Testdata: 3 ~ 3, Score: 15
For Testdata: 4 ~ 4, Score: 20
For Testdata: 5 ~ 10, Score: 30
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 262144 65536
1 1000 262144 65536
2 1000 262144 65536
3 1000 262144 65536
4 2000 262144 65536
5 4000 262144 65536
6 4000 262144 65536
7 2000 262144 65536
8 2000 262144 65536
9 4000 262144 65536
10 4000 262144 65536