【AOJ 2007】Make Purse Light
問題
Make Purse Light | Aizu Online Judge
ソースコード
#include <iostream> #include <algorithm> using namespace std; #define rep(i,n) for(int i = 0 ; i < n ; i++) int coin[4]; int min_coin[4]; int d[] = {10, 50, 100, 500}; int out[4]; int main(){ int m; bool flag = false; while(cin >> m, m){ cin >> coin[0] >> coin[1] >> coin[2] >> coin[3]; int min = 100000000; if(flag) cout << '\n'; for(int i = 0 ; i <= coin[0] ; i++){ for(int j = 0 ; j <= coin[1] ; j++){ for(int k = 0 ; k <= coin[2] ; k++){ for(int l = 0 ; l <= coin[3] ; l++){ int sum = 0; fill(out, out+4, 0); sum = i * d[0] + j * d[1] + k * d[2] + l * d[3]; if(sum < m) continue; sum -= m; for(int a = 3 ; a >= 0 ; a--){ while(d[a]<=sum){ sum -= d[a]; out[a]++; } } int hoge=0; rep(a, 4){ hoge = hoge + out[a] + coin[a]; } hoge -= (i+j+k+l); if(hoge < min){ min_coin[0] = i; min_coin[1] = j; min_coin[2] = k; min_coin[3] = l; min = hoge; } } } } } rep(i, 4){ if(min_coin[i] > 0){ cout << d[i] << " " << min_coin[i] << "\n"; } } flag = true; } }
全通り試しました。もっと簡単に求まるみたい。ソースコードはとても書き直したい。