2013年9月28日 星期六

1199 - Elevator Stopping Plan

在 ZSoft Corp 這家公司中,每名員工都相當地勤奮,但是電梯問題總是困擾他們。
因為這家公司只有一台電梯運作,使得在早上的時候,總是會花很多時間在等待電梯。

Hal 相當聰明,想要改善這種情況,目標要把電梯改為更有效率,但這並不是簡單的工作。

公司總共有 31 樓,電梯上升一樓消耗 4 秒,也就是說將會使用 (31 - 1) ×4 = 120 秒到達頂樓,如果電梯打算停留某一層時,將會額外消耗 10 秒時間停止。如果電梯每層都停,將會消耗 30×4 + 29×10 = 410 秒 (不考慮停留在 31 樓)。

員工們可以打算爬樓梯,不管是往上或往下爬一層,都是消耗 20 秒。如果從 1 樓爬到 31 樓,則消耗 30×20 = 600 秒。當然,只爬樓梯肯定不是最好的方式。因此一些員工會使用電梯到達某一層之後,再爬樓梯到達他們自己的辦公室。

經過一段時間精密的思考後,Hal 最後找到一個方法改善這種情況。首先,電梯會先問所有人要到達的樓層,將會設計停留哪一層的方案,最小化最後一個人到達的時間。

例如,電梯被要求停留在第 4, 5, 10 樓時,停留方案為
1. 先停留於第 4 樓,此時消耗 3×4 = 12 秒,並且停止 10 秒。
2. 之後直接抵達 10 樓,此時時間為
3×4 + 10 + 6×4 = 46 秒。

到抵達 4 樓人在 12 秒時可以到達,抵達 5 樓的人可以在 12 + 20 = 32 秒,而要抵達 10 樓的人將在 46 秒後到達。


寫程式計算最小化最後一個人抵達的時間,並且輸出停留方案。

Input 

輸入有多組測資。

每組測資的格式如下:

n f1 f2 ... fn
將會有 n 個樓層被要求停留, f1 f2 ... fn 表示為要求停止的樓層。
 (n <= 30, 2 <= f1 < f2 < ... < fn <= 31)

Output 

對於每組測資,輸出一行最小的最後一個人抵達的時間。

第二行,先輸出停留樓層的個數,再分別輸出停留樓層的編號。

如果有多組輸出,任何一組都可以。

Sample Input 


3 4 5 10
1 2
0

Sample Output 


46
2 4 10
4
1 2

沒有留言:

張貼留言