AOJ_1028 ICPC: Ideal Coin Payment and Change
問題
解法
代金をpとすると,実際に払う金額Pは p <= P <= p+500 の範囲にあるはず.
だから,全部ためしていくといい.
#include <cstdio> #include <algorithm> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) const int INF = 1 << 30; const int coin[6] = { 1, 5, 10, 50, 100, 500 }; int N[6]; int p; int solve(int p){ int n[6], res = 0; REP(i,6) n[i] = N[i]; while(true){ if(p == 0) break; bool f = true; for(int i = 5; i >= 0; i--){ if(p >= coin[i] && n[i] > 0){ n[i]--; p -= coin[i]; res++; f = false; break; } } if(f) return INF; } return res; } int change(int d){ int res = 0; REP(i,6){ res += d / coin[5-i]; d = d % coin[5-i]; } return res; } int main(){ while(scanf("%d", &p) && p){ REP(i,6) scanf("%d", &N[i]); int ans = INF; for(int P = p; P <= p + 500; P++){ ans = min(ans, solve(P) + change(P - p));; } printf("%d\n", ans); } return 0; }