TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

100.0% (96/96)

Submission's AC Ratio

86.7% (124/143)

Tags

Description

乖小孩都可以在聖誕夜收到聖誕老人送的禮物。但是乖小孩這麼多,聖誕老人能夠在時間內將禮物送完,是有訣竅的。聖誕老人藉由他的法力,不但可以讓馴鹿拉著裝滿禮物的雪橇飛上天際,還可以將空間扭曲,將乖小孩們的住處排列在一直線上,然後將雪橇加速到光速,很快的將一整雪橇的禮物送完。
雖然聖誕老人有很強的法力,但麻煩的是馴鹿要吃草。在連續飛行x公里後,馴鹿必須吃x2公斤的牧草,才願意繼續飛行。萬一在送完禮物之前的某次著陸時,沒有足夠的牧草給馴鹿吃,馴鹿是會罷工的,那麼有些乖小孩就收不到聖誕禮物了。所以精靈們必須將乖小孩所在的位置經過空間扭曲之後的座標清單算好,長度單位以公里計,並且計算好每次降落後要準備多少牧草給馴鹿吃,再將這些資料交給聖誕老人。
你現在是精靈工廠的電腦工程師,負責計算聖誕老人必須準備多少牧草,才能從北極出發,而順利送完禮物給所有在清單上的乖小孩。假設空間扭曲成直線後,聖誕老人出發的座標是0,接著聖誕老人會選擇路程最短的方式送禮物,也就是座標小的先送,座標大的後送。例如:如果乖小孩有2位,座標分別是5和17,那麼聖誕老人會先送給座標5的乖小孩,再送給座標17的乖小孩,一共需要準備52 + (17-5)2 = 169公斤的牧草。
因為資料量很大,就算作為一個精靈,也無法拿紙筆計算,你必須寫一個程式來計算聖誕老人需要準備多少牧草給馴鹿吃。

Input Format

輸入的第一行為一個小於10000正整數n,代表這一雪橇的禮物一共要送給n個乖小孩。緊接的有n行,每行都恰有一個正整數,代表某個乖小孩的家經過空間扭曲後在直線上的座標(假設這n個正整數皆不相同)。在直線座標上,每個乖小孩與距他最近的乖小孩不會超過100公里,而距出發點最近的乖小孩也在100公里內。

Output Format

輸出聖誕老人需要準備多少公斤的牧草。

Sample Input 1

輸入範例1: 5 50 150 199 99 225

輸入範例2: 5 5 3 4 2 1

輸入範例3: 5 100 50 98 2 1

Sample Output 1

輸出範例1: 10579

輸出範例2: 5

輸出範例3: 4614

Hints

※2008/03/20:範例輸入及題目敘述修正。感謝Tommy。

Problem Source

原TIOJ1141 / 95全國賽(prob 2)。

Subtasks

No. Testdata Range Score
1 0 20
2 1 20
3 2 20
4 3 20
5 4 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
1 3000 65536 262144 2
2 3000 65536 262144 3
3 3000 65536 262144 4
4 3000 65536 262144 5