e591: 11264 - Coin Collector
Tags : Greedy
Accepted rate : 4人/4人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2019-10-31 13:47

Content

Sultan到某個國家旅行,那裡有n種不同類型的硬幣。
他想儘可能蒐集最多種不同類型的硬幣。如果他想從銀行提取X筆錢,銀行將使用以下算法將這筆錢給他:

withdraw(X) {
    if(X == 0)
        return;
    令 Y 為其值不超過 X 且面額最大的硬幣。
    給客戶一個 Y 元的硬幣。
    withdraw(X-Y);
}

現在Sultan可以從銀行提取任意金額。他想要在一次提款中蒐集最多種不同類型的硬幣。

Input

輸入的第一行包含一個整數T,代表測資數量。
每組測資第一行有一個整數n (1 ≤ n ≤ 1000),代表不同類型硬幣的數量。
下一行包含n個整數C1、C2、...、Cn,分別代表每種硬幣的面額。
其中C1 < C2 < C3 < ... < Cn < 1000000000,且C1 = 1。

Output

對於每組測資,輸出Sultan一次提款最多可以從銀行拿到幾種不同的硬幣。

Sample Input
2
6
1 2 4 8 16 32
6
1 3 6 8 15 20
Sample Output
6
4
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (50%): 1.0s , <1M
公開 測資點#1 (50%): 1.0s , <1M
Hint :
Tags:
Greedy
出處:
UVA [管理者:
ig99lp33lp33 (원스)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」