TopCoder

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

User's AC Ratio

89.7% (26/29)

Submission's AC Ratio

53.3% (40/75)

Tags

Description

是的...從前從前,有個人叫做霍夫...
自從他學了神秘的編碼學以後,他開始不誤正業了(誤)!
他把所有他看到的東西通通編了碼...

是的!你的任務就是要改變霍夫快編碼的壞習慣,要搶先一步,在他把測資通通編碼之前先把它解決掉!
給你一篇文章中n種字元出現的次數,現在採用「三進位編碼」,也就是這n種字元每一種可以被編為包含0,1,2的序列。
相同地,每一個字元編碼後,都不可以是其他編碼後字元的前綴字串(prefix),例如 012 與 01210 是不合法的編碼方式。
請問將這篇文章以最佳方式編碼後的文章長度為何?

Input Format

輸入可能包含多筆測試資料,以EOF作結束。

每筆測試資料的第一列有一個正整數n(1≦n≦100,000),代表文章中有幾種字元。

接下來有n個正整數,分別代表每一種字元於文章中出現的次數,這些數字都不會超過 1,000,000。

Output Format

對於每一筆測試資料請輸出一列,包含一個數字:以最佳方式編碼後的文章長度。

Sample Input 1

4
10 15 20 100
5
1 2 3 4 5

Sample Output 1

170
21

Hints

Problem Source

原TIOJ1398 / 快樂暑假營第四次練習比賽。Problem Setter:Tmt。

Subtasks

No. Testdata Range Score
1 0 25
2 1 25
3 2 25
4 3 25

Testdata and Limits

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