7495. Цифры

Маленький Петя любит целые числа. Недавно он изучил различные свойства сумм цифр числа. Например, если сумма цифр числа делится на 9, то и само число делится на 9.

Сейчас маленького Петю интересуют числа с одинаковой суммой цифр. Он просит старшего брата Диму найти n натуральных чисел с одинаковой суммой цифр и наименьшей возможной общей суммой. У Димы есть другие дела, поэтому он попросил Вас написать программу, решающую эту задачу.

Вход. Содержит одно целое число n (1 ≤ n ≤ 5000).

Выход. Вывести наименьшую возможную сумму n натуральных чисел, сумма цифр которых одинакова.

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

РЕШЕНИЕ

перебор

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

Для каждого числа i (1 ≤ i ≤ 10⁶) посчитаем его сумму цифр s. Построим список смежности v, где v[s] содержит все натуральные числа до 10⁶ с суммой цифр s. При этом все числа в массивах v[s] остортируем по возрастанию.

Для нахождения результата найдем суммы n наименьших чисел из каждого v[s] (при этом нас не интересуют такие v[s], которые содержат меньше чем n чисел). Минимальная среди найденных сумм и будет искомой.

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

Объявим константу и список смежности v для хранения чисел.

#define MAX 1000010

vector<vector<int> > v;

Вычисляем сумму цифр числа n.

int sum(int n)

{

int s = 0;

while(n > 0)

{

s += n % 10;

n /= 10;

}

return s;

}

Основная часть программы. Занесем в v[s] числа от 1 до 10⁶ с суммой цифр s. В процессе построения списка смежности массивы v[s] уже являются отсортированными по возрастанию.

v.resize(MAX);

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

{

s = sum(i);

v[s].push_back(i);

}

Читаем входное значение n. Для каждого массива v[i], содержащего хотя бы n чисел, находим сумму n наименьших чисел. Среди всех таких сумм находим минимальную.

scanf("%d",&n);

res = (long long)1e18;

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

if (v[i].size() >= n)

res = min(res,accumulate(v[i].begin(),v[i].begin()+n,0LL));

Выводим ответ.

printf("%lld\n",res);