TopCoder

Thumb 100
tmwilliamlin
我的中文很爛

User's AC Ratio

80.0% (4/5)

Submission's AC Ratio

22.7% (5/22)

Description

題目在這裡

Dark Kingdom 的一大特色就是非常奇異的錢幣。
負責鑄造王國錢幣的 Darkseer 當時正在研究黑魔法,他把他一小部分的成果 在一堆石頭上實作,於是產生了 Dark Kingdom 著名的邪惡硬幣。

這些硬幣的幣值分別是 Dark Number 的前 52 項: 1, 2, 3, 4, 6, 9, 13, 19, 28, 41, 60, 88, 129, 189, 277, 406, 595, 872, 1278, 1873, 2745, 4023, 5896, 8641, 12664, 18560, 27201, 39865, 58425, 85626, 125491, 183916, 269542, 395033, 578949, 848491, 1243524, 1822473, 2670964, 3914488, 5736961, 8407925, 12322413, 18059374, 26467299, 38789712, 56849086, 83316385, 122106097, 178955183, 262271568, 384377665

現在可怕的事情是,如果把兩個相同的硬幣放在一起,他們就會彼此吸引對方, 直到碰在一起為止... 然後爆炸!所以大家根本不敢帶相同的硬幣在身上, 這也就是為什麼這些硬幣被稱為邪惡硬幣的原因。

除此之外,每個硬幣還有個魔力消耗值,一個硬幣的魔力消耗值一定是整數, 不會超過該硬幣的幣值,且至少有該硬幣幣值的 1/2。 (例如,幣值 1 的硬幣的魔力消耗值必為 1,幣值 3 的硬幣的魔力消耗值可能是 2 或 3)

於是 Dark Kingdom 裡的商店就常常傷腦筋,他們在找錢給顧客時, 得幫顧客找一個總魔力消耗值最小的方式,因此他們請你寫一個程式幫他們解決問題。

Input Format

輸入包含多組測試資料。 每組第一行是一個正整數 N(1≦N≦1209982072),表示得要找給客人的總幣值。第二行可能有 1~52 個正整數。分別從幣值小到大,依序表示可能使用到的硬幣的魔力消耗值。(不可能使用到的意思是硬幣的幣值超過 N)

Output Format

輸出一行正整數,表示最小的總魔力消耗值。

Sample Input

3
1 1 2
10
1 2 3 2 6 9

Sample Output

2
8

Hints

2015/8/1 將連結的內容搬到網頁上

Problem Source

原TIOJ1131 / [KSHSVC] 雄中公假社'07 公開賽。Problem Setter:Darkseer。

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 5000 65536 262144 1