e591.
11264 - Coin Collector
內容
Sultan到某個國家旅行，那裡有n種不同類型的硬幣。
他想儘可能蒐集最多種不同類型的硬幣。如果他想從銀行提取X筆錢，銀行將使用以下算法將這筆錢給他：
withdraw(X) {
if(X == 0)
return;
令 Y 為其值不超過 X 且面額最大的硬幣。
給客戶一個 Y 元的硬幣。
withdraw(X-Y);
}
現在Sultan可以從銀行提取任意金額。他想要在一次提款中蒐集最多種不同類型的硬幣。
輸入說明
輸入的第一行包含一個整數T，代表測資數量。
每組測資第一行有一個整數n (1 ≤ n ≤ 1000)，代表不同類型硬幣的數量。
下一行包含n個整數C1、C2、...、Cn，分別代表每種硬幣的面額。
其中C1 < C2 < C3 < ... < Cn < 1000000000，且C1 = 1。
輸出說明
對於每組測資，輸出Sultan一次提款最多可以從銀行拿到幾種不同的硬幣。
範例輸入
#1
2 6 1 2 4 8 16 32 6 1 3 6 8 15 20
範例輸出
#1
6 4
測資資訊：
記憶體限制：
64
MB
公開 測資點#0 (50%): 1.0s , <1M
公開 測資點#1 (50%): 1.0s , <1M
公開 測資點#0 (50%): 1.0s , <1M
公開 測資點#1 (50%): 1.0s , <1M
提示 ：
標籤:
出處:
UVA
[管理者：
ig99lp33lp33
(위즈원)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
| 37672 |
|
e591 | 333 | 2023-09-27 16:31 |