【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;
  }

}

全通り試しました。もっと簡単に求まるみたい。ソースコードはとても書き直したい。