009 - 重商主義
時間制限 1 秒 / メモリ制限 64 MB / 得点 400 / x 9 /
この問題は部分点があります。
問題
資本家を否定しようと思うものは、資本家たちの貨幣を破壊しなければならない。
── ウラジーミル・イリイチ・レーニン
3種類の相異なる金額のコインが∞枚あります。
それを使ってN円をちょうど払うとき、最小で何枚のコインが必要ですか。
求めてください。
ただし、どのようにしてもちょうど払えないときは-1を出力してください。
入力
money1 money2 money3 N
一行目に3種類のコインの金額が与えられます。
次に払う金額Nが与えられます。
出力
minCoin
制約と部分点
テストケースのうち点数の25%分は以下の制約を満たします。$1$ ≤ $money$i ≤ $10$2
$1$ ≤ $N$ ≤ $10$2
テストケースのうち点数の75%分は以下の制約を満たします。
$1$ ≤ $money$i ≤ 5 * $10$3
$1$ ≤ $N$ ≤ 5 * $10$3
テストケース
例1
入力
1 2 3 1
出力
1
1円のコイン1枚でちょうど払えます。
例2
入力
1 2 3 7
出力
3
1円のコイン1枚と3円のコイン2枚
2円のコイン2枚と3円のコイン1枚
のどちらかで払うことができます。