2013年8月16日

UVa 11005 - Cheapest Base

#include <cstdio>
#include <cstring>

int p[37], cost[37];

void cal(int n, int b) {
  if (!n) {
    return;
  }
  cal(n / b, b);
  cost[b] += p[n % b];
}

int main() {
  int T, C = 1;
  scanf("%d", &T);
  while (T--) {
    for (int i = 0; i < 36; i++) {
      scanf("%d", &p[i]);
    }
    int n;
    scanf("%d", &n);
    printf("Case %d:\n", C++);
    while (n--) {
      memset(cost, 0, sizeof(cost));
      int num, min = 2e9;
      scanf("%d", &num);
      for (int b = 2; b < 37; b++) {
        cal(num, b);
        min = cost[b] < min ? cost[b] : min;
      }
      printf("Cheapest base(s) for number %d:", num);
      for (int b = 2; b < 37; b++) {
        if (cost[b] == min) {
          printf(" %d", b);
        }
      }
      puts("");
    }
    if (T) {
      puts("");
    }
  }
  return 0;
}

沒有留言:

張貼留言