2010年9月17日 星期五

ACM 11005 - Cheapest Base

#include <stdio.h>
#include <ctype.h>
#define SIZE 37
int index, best[SIZE];
int money[SIZE];

int getMoney(int n, int base)
{
int nMoney = 0;
for (; n; n /= base)
{
nMoney += money[n % base];
}
return nMoney;
}

int main()
{
int n, i, m, j, k, min, count, caseNum;
scanf("%d", &n);
for (caseNum = 1; caseNum <= n; caseNum ++)
{
if (caseNum != 1) printf("\n");
index = 0;
for (i = 0; i < 36; i ++)
scanf("%d", &money[i]);
printf("Case %d:\n", caseNum);
scanf("%d", &m);
for (i = 0; i < m; i ++)
{
scanf("%d", &k);
index = 0;
min = getMoney(k, 2);
best[index ++] = 2;
for (j = 3; j <= 36; j ++)
{
count = getMoney(k, j);
if (min == count) best[index ++] = j;
if (min > count) min = count, index = 0, best[index ++] = j;
}
printf("Cheapest base(s) for number %d:", k);
for (j = 0; j < index; j ++)
printf(" %d", best[j]);
printf("\n");
}
}
return 0;
}


回目錄
回首頁

沒有留言 :

張貼留言

Related Posts Plugin for WordPress, Blogger...