задача на ограничение числа операций

[nastymauz]

У Кости есть бумажка, на которой написано n чисел. Также у него есть возможность не больше, чем k раз, взять любое число с бумажки, после чего закрасить одну из старых цифр, а на ее месте написать новую произвольную цифру.
На какое максимальное значение Костя сможет увеличить сумму всех чисел на листочке?

Формат входных данных
В первой строке входного файла даны два целых числа n,k — количество чисел на бумажке и ограничение на число операций.
(1≤n≤1000,1≤k≤10000)
Во второй строке записано n чисел a(i)(1≤a(i)≤10^9)
например:
ввод:........ вывод:
3 1 ........... 10
99 5 85
как это решить?

 

[Vershitel_sudeb]

Берёшь массив чисел, сортируешь по убыванию, потом по порядку заменяешь в каждом числе сначала первый разряд, потом второй, и т. д. на 9

Например:
Дано (5 операций)
[5, 32, 120, 69, 1]

Сортируем
[120, 69, 32, 5, 1]

Сначала меняем все сотни на 9
[920, 69, 32, 5, 1]

Потом все десятки (осталось 4 операции)
[990, 99, 92, 5, 1]

Потом все единицы (осталась одно операция)
[999, 99, 92, 5, 1]

 

[barsty]

Берёшь массив чисел, сортируешь по убыванию, потом по порядку заменяешь в каждом числе сначала первый разряд, потом второй, и т. д. на 9

Например:
Дано (5 операций)
[5, 32, 120, 69, 1]

Сортируем
[120, 69, 32, 5, 1]

Сначала меняем все сотни на 9
[920, 69, 32, 5, 1]

Потом все десятки (осталось 4 операции)
[990, 99, 92, 5, 1]

Потом все единицы (осталась одно операция)
[999, 99, 92, 5, 1]

Если массив будет:
[5, 32, 120, 530, 840, 69, 1]

После сортировки получим:
[840, 530, 120, 69, 32, 5, 1]

после операций замены:
[990, 990, 920, 69, 32, 5, 1] вместо нужных:
[940, 990, 990, 69, 32, 5, 1]

 

[Vershitel_sudeb]

mas = [5, 32, 120, 530, 840, 69, 1]
suma = sum(mas)

# Записываем числа как строки, дополняя спереди нулями
mas = list(map(lambda x: str(x).zfill(len(str(max(mas)))), mas))

oper = 5
ind = 0
while True:
    # Сортируем массив по возростанию первой цифры (потом второй, и т.д.)
    mas.sort(key=lambda x: x[ind])
    # Проходим по массиву
    for n, i in enumerate(mas):
        # Если замены кончились, завершаем цикл
        if oper == 0:
            break
        # Если разряд который мы будем менять не равен 9
        # И при этом он значащий (то есть не 0 в числе 005 например)
        if set(i[:ind+1]) != {'0'} and i[ind] != '9':
            # Заменяем в числе нужную цифру на 9
            el = list(i)
            el[ind] = '9'
            mas[n] = ''.join(el)
            oper -= 1
    else:
        # Переходим к следующему разряду
        ind += 1
        continue
    break
mas = list(map(int, mas))
# Выводим массив
print(sorted(mas))
# И на сколько он увеличился
print(sum(mas) - suma)

 

[kislyakoff]

Сам столкнулся с этой задачей, долго голову ломал. Нашел подсказку, как все элегантно сделать без перевода в символьный массив.
Идея в том, чтобы вычислить дельту которая добавится при изменении каждого из разрядов на 9 поочередно. Сохранить все дельты (или для экономии памяти первые k максимальных дельт - реализация уже от возможностей языка зависит) и сложить результат, который и будет ответом.

Процесс вычисления дельт поразрядно довольно прост - его можно встроить прямо в цикл считывания входных значений, извините, что фрагмент из Java, но думаю все интуитивно понятно:

int t = scanner.nextInt(); // число из входного массива в цикле обрабатываем по очереди              
int weight = 1; // так как идем справа-начальный весовой коэф 1
    while (t > 0) {
        int digit = t % 10; // работаем с остатком от деления на 10
        long gain = (9 - digit) * weight;
        // здесь добавляете gain в удобный для вас класс-коллекцию,
        // которую можно отсортировать и выбрать макс. k значений и суммировать
        weight *= 10; // двигаемся на весовой разряд влево
        t /= 10; // целоисчисленно отсекаем правую цифру
    }

возможно кому-то будет полезно.