TopCoder

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

66.7% (2/3)

Tags

Description

在一個大地遊戲中,由左到右有 $N$ 個彼此相距一公尺的攤位。一開始挑戰者在最左邊的攤位左方一公尺處。

在遊戲計時開始後,從左數來第 $i$ 個攤位會從第 $0$ 秒開始每隔 $T_i$ 秒投影一瞬間的綠光。如果挑戰者在此攤位面前被此攤位的綠光照到,就視為通過這個攤位的關卡。每一秒鐘挑戰者可以往左走一公尺、往右走一公尺或是留在原地,挑戰者需要通過全部 $N$ 個關卡各至少一次,結束時可以在任意位置。

請回答挑戰者至少要花多少時間。

Input Format

輸入第一行是一個整數 $N$,代表攤位數。

第二行是 $N$ 個整數,代表題目所述的 $T_i$。

輸入保證 $1\le N\le 16$,$1\le T_i\le 10^ 8$。

Output Format

輸出一行一個整數代表最快完成時間。

Sample Input 1

3
7 4 3

Sample Output 1

7

Sample Input 2

4
8 7 6 3

Sample Output 2

12

Hints

Problem Source

TIOJ

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~14 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2