1, 5, 10, 50, 100, 500 円玉がある日本では、ある金額を支払う時、大きい金額の硬貨をできるだけ多く使うという方法で支払うと、硬貨の枚数を最小化できることが知られている。
硬貨の金額が日本とは異なる場合、貪欲に支払うと必ずしも最小化できるとは限らない。
貪欲に支払うのが最適になるために、硬貨の金額が満たすべき条件は何なのだろうか。
TAB 君は上のことが気になったので、まずは硬貨が 1, A, B の 3 種類しかない場合について考えることにした。
A, B が与えられるので、貪欲に支払った場合枚数が最小にならないような金額のうち、最小のものを出力せよ。
また、どんな金額でも貪欲法が最適な場合は、-1 を出力せよ。
A B
4 6
8
8 円を貪欲に支払うと、 6 + 1 \times 2 で支払うことになり、合計 3 枚必要だが、4 \times 2 で合計 2 枚で支払うことができる。
2 1000000000
-1
どんな金額であっても貪欲に支払うのが最適である。