2013年3月21日

UVa 166 - Making Change


#include <stdio.h>

int v[6] = {5, 10, 20, 50, 100, 200}, num[6], cost, min;

int need(int n) {
  int i, used = 0;
  for (i = 5; i >= 0; i--)
    if (n >= v[i]) {
      used += n / v[i];
      n = n % v[i];
    }
  return used;
}

void solve(int now, int sum, int used) {
  if (now == 6) {
    if (sum >= cost) {
      used += need(sum - cost);
      if (used < min) min = used;
    }
    return;
  }
  int i;
  for (i = 0; i <= num[now]; i++)
    solve(now + 1, sum + i * v[now], used + i);
}

int main() {
  while (scanf("%d%d%d%d%d%d", &num[0], &num[1], &num[2], &num[3], &num[4], &num[5]) && (num[0] + num[1] + num[2] + num[3] + num[4] + num[5])) {
    double tmp;
    scanf("%lf", &tmp);
    cost = tmp * 100;
    min = 2e9;
    solve(0, 0, 0);
    printf("%3d\n", min);
  }
  return 0;
}

沒有留言:

張貼留言