Что требуется в задаче Python?

Question

[KIPPY]

Подобные задачи заводят меня в тупик. Даже не понимаю, что требуется от программы. Что она должна делать?
Буду признателен, если кто объяснит что к чему. Или порекомендует ресурсы, где можно глянуть.
В интернете лопатил - безрезультатно.

Comments

[Roman K]

Обычное олимпиадное программирование. Ресурсов, где можно практиковаться — валом. Любой online judge: codeforces, leetcode и т.п.

Answer 1

[Vindicar]

В первой задаче всё достаточно просто.
1) чтобы понять, насколько мы увеличим сумму чисел, достаточно посчитать сумму до и после преобразования. Так что задач сводится к "максимизировать сумму чисел, меняя в них цифры"
2) Чтобы максимизировать сумму, надо максимизировать слагаемые. Так что нужно как можно сильнее увеличить числа, заменив одну цифру за раз.
3) Как увеличить число как можно сильнее? Нужно заменить старший разряд в числе на девятку, это даст наибольший эффект.
4) Тонкость раз: если старший разряд уже девятка, нам нужен следующий разряд, и т.д. пока не найдём НЕ девятку. Если число из одних девяток, его игнорируем.
5) Тонкость два: если у нас есть числа 12 и 123, то больший эффект будет достигнут увеличением второго, т.к. у него старший разряд больше.
6) Тонкость три: если у нас есть числа 123 и 456, то больший эффект будет достигнут увеличением первого, т.к. у него старший разряд имеет меньшее значение.

Отсюда логика решения: для каждого числа ищем старший разряд, не равный 9. Фиксируем сведения о числе, номере разряда (единицы, десятки, сотни и т.п.), и цифре в разряде.
В списке найденных "кандидатов на замену" убираем все варианты, где номер разряда меньше максимального в списке (т.е. если у кого-то можно заменить сотню, то десятки и единицы уже не рассматриваем). Этот шаг можно совместить с генерацией списка.
Из оставшихся кандидатов ищем того, у кого цифра в разряде наименьшая. Эту цифру в этом числе и заменяем на девятку.
Прирост числа, а значит и прирост общей суммы, будет равен (9 - старая цифра) * вес разряда. Например, заменили в сотнях 2 на 9, получим прирост (9 - 2) * 100 = 700.

Процесс повторяем k раз, прирост накапливаем.

Answer 2

[Wataru]

Перечитайте условие медленно. Посмотрите пример.

В первой задаче надо выбрать какие-то числа, в числах выбрать какие-то цифры (всего не более k цифр) и заменить их другими цифрами так, чтобы сумма увеличилась как можно больше. Очевидно, что заменять надо старшие цифры и всегда на 9. Поэтому можно сразу сказать, что если мы в числе 128694 заменяем 3 цифры - то это "128" и получится 999694.

Особый случай тут, если число содержит девятки - их надо пропустить.

Теперь задача немного упрощается. Надо распределить k цифр по числам, чтобы получить максимум профита, т.е. увеличить максимально сумму чисел.

Можно еще немного порисовать тесты на бумажке и понять, что каждое число можно рассматривать как набор цифр. Каждая цифра отдельна. Ибо замена одной цифры увеличит сумму на (9-цифра)*10^(разряд цифры) независимо от остальных цифр. Т.е. задача еще преобразуется - есть куча цифр каждая с известным профитом, если ее заменить. Надо не более k из них взять, так что бы сумма изменения была максимальна.

Теперь понятно, что задача решается сортировкой. Считатете для каждой цифры сумму профита, все это складываете в массив (длины максимум 10*n). Сортируете по убыванию и берете сумму первых k значений.

Вотрая задача - опять же медленно читайте. Я не могу за вас понять. Объяснить как-то проще условие тоже не могу. Попробуйте порисовать тесты в виде пронумерованных точек, от которых стрелочки идут к значению a[i] - кому они дают подарки. Вам надо ровно одну стрелочку переместить так, что бы все стрелочки замкнулись в один круг.

Для решения надо понять, а что будет, если не менять ни одно число? Путь из точки 1 будет или циклом или чем-то вроде цифры "6". Сначала какой-то хвост, который зацикливается где-то на середине.

Во втором случае понятно что делать - надо последний шаг завернуть назад на начало хвоста, вместо середины. Если при этом в пути уже все вершины, то это ответ.

В первом случае сложнее. Если путь уже проходит через все вершины, то ничего не сделать. Если что-то изменить цикла по всем вершинам не получится. Если же там не все вершины, то замена должна пойти в какую-то невключенную вершину, обойти их все и вернутся к циклу. Поэтому надо найти единственную вершину, в которую не ведет ни одна стрелка, убедится, что путь от нее пройдет все не включенные в цикл вершины и воткнется в цикл. И тогда надо предыдущую стрелку перед точкой втыкания в цикл развернуть на начало внешнего пути.

Answer 3

[longclaps]

Что-то KIPPY затих, ответы штудирует )
Смотри, вот не совсем решение первой задачи а, скорее, иллюстрация к разъяснениям Vindicar и Wataru :

from random import randrange

data, res = [str(randrange(1000)) for _ in range(10)], 0
for le in range(max(len(s) for s in data), 0, -1):
    print('data:', *data)
    head, tail = [], []
    for s in data:
        (head if len(s) < le else tail).append(s)
    data = head
    for s in sorted(tail):
        data.append(s[1:])
        if s[0] != '9':
            t = '9' + s[1:]
            delta = int(t) - int(s)
            res += delta
            print(f'{s:>4} -> {t:<4}  {delta:>4}')
print(f'    итого{res:>9}')