11005. Самое дешевое основание

Для написания чисел используют чернила. Числа могут записываться в разных системах исчисления: от двоичной до 36-ичной, где используются символы от 0 до 9 и от a до z. Известна стоимость чернил для написания каждого символа. Стоимость написания числа равна сумме стоимостей написания входящих в него символов. Необходимо найти такую систему основания, запись в которой заданного числа требует наименьшей стоимости чернил.

Вход. Первая строка содержит количество тестов n (n £ 25). Четыре первые строки по девять чисел задают стоимость написания символов 01…89ab…yz. Далее следует количество запросов и сами запросы – числа, заданные в десятичной системе исчисления. Все числа не меньше 0 и не больше 2*10⁹.

Выход. Для каждого теста вывести его номер. Для каждого входного числа вывести в порядке возрастания все системы основания, запись его в которых требует наименьшей стоимости чернил. Между тестами выводить пустую строку.

Пример входа

2

10 8 12 13 15 13 13 16 9

11 18 24 21 23 23 23 13 15

17 33 21 23 27 26 27 19 4

22 18 30 30 24 16 26 21 21

5

98329921

12345

800348

14

873645

1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1

1 1 1 1 1 1 1 1 1

4

0

1

10

100

Пример выхода

Case 1:

Cheapest base(s) for number 98329921: 24

Cheapest base(s) for number 12345: 13 31

Cheapest base(s) for number 800348: 31

Cheapest base(s) for number 14: 13

Cheapest base(s) for number 873645: 22

Case 2:

Cheapest base(s) for number 0: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

Cheapest base(s) for number 1: 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

Cheapest base(s) for number 10: 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

Cheapest base(s) for number 100: 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

РЕШЕНИЕ

полный перебор

Анализ алгоритма

Для каждого основания от 2 до 36 следует вычислить стоимость чернил для написания заданного числа. Далее найти те основания, для которых эта стоимость наименьшая.

Реализация алгоритма

В массиве cost храним стоимость написания букв (cost[0] соответствует символу 0, cost[35] – символу z).

int cost[36];

Функция FindCost возвращает стоимость написания числа n в системе исчисления с основанием base.

int FindCost(int n, int base)

{

int res = 0;

while(n > 0)

{

res += cost[n%base];

n /= base;

}

return res;

}

Основная часть программы. Читаем количество тестов tests.

scanf("%d",&tests);

for(i = 1; i <= tests; i++)

{

Читаем стоимости написания символов в массив cost.

for(j = 0; j < 36; j++) scanf("%d",&cost[j]);

Читаем количество запросов к тесту n. Выводим номер теста.

scanf("%d",&n);

printf("Case %d:\n",i);

while(n--)

{

Для каждого входного числа num перебираем все возможные основания систем исчисления от 2 до 36, находим в какой из них стоимость написания числа num наименьшее. Искомую стоимость храним в переменной min.

scanf("%d",&num);

printf("Cheapest base(s) for number %d:",num);

min = 2000000000;

for(j = 2;j <= 36; j++)

{

temp = FindCost(num,j);

if (temp < min) min = temp;

}

Ищем основания, для которых стоимость написания числа num равна min. Выводим их в порядке возрастания.

for(j = 2; j <= 36; j++)

if (min == FindCost(num,j)) printf(" %d",j);

printf("\n");

}

Между тестами выводим пустую строку.

if (i < tests) printf("\n");

}