TopCoder

Thumb hsnu2016
Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

66.7% (20/30)

Submission's AC Ratio

19.4% (24/124)

Description

  考慮以下的「河內之塔」的一種變化型態。一平面上豎著A,B,C三根小木樁,其中的木樁A由上而下套著一些圓環,共有若干種尺寸,每種尺寸的圓環各有若干個,由小而大排列,如圖所示。假設相同尺寸的圓環都不一樣(如下圖所示,我們可將圓環由上而下編號為1、2、3、…)。現在我們想要將所有這些圓環由木樁A搬到木樁C,而使得最後在木樁C上面的圓環編號由上而下仍為1、2、3、…。搬動的規則如下:

(a) 一次只能搬動一個圓環。
(b) 每次搬動都須由某根木樁搬到另一根木樁,圓環不能被暫時放到非木樁的其他地方。
(c) 對任何木樁上任意兩個相鄰圓環而言,上面的圓環一定不能比下面的圓環大。
  此題便是要請你設計一個程式來求出最少須搬移的次數。以下圖為例,最小尺寸的圓環有1個,次小的有2個,最大的圓環有1個。圖中所顯示的搬移方式是最佳解,共須搬移9次。

條件限制:
圓環的尺寸種類最少1種,最多10種。每種圓環的數量介於1至10個之間。

Input Format

輸入檔可能包含非常大量的測試資料。
每一筆測試資料的第一列有一個正整數k,表示有k種尺寸的圓環。
第二列有k個正整數,表示由小到大之尺寸各自的圓環數量,正整數之間以空白隔開。

Output Format

對於每筆測試資料請輸出滿足題目所求之最小搬動次數。

Sample Input

3
1 2 1
5
1 1 1 1 1

Sample Output

9
31

Hints

Problem Source

原TIOJ1119 / 92北市賽(prob 5)。Special thanks:kelvin。

Subtasks

For Testdata: 0 ~ 0, Score: 50
For Testdata: 1 ~ 1, Score: 50
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144
1 1000 65536 262144