What is required in a Python task?

Question

Python

Problems like this drive me crazy. I do not even understand what is required from the program. What should she do?
I would be grateful if someone could explain what's what. Or recommend resources where you can look.
I have scoured the Internet - to no avail.

Answer 1

In the first task, everything is quite simple.
1) to understand how much we will increase the sum of numbers, it is enough to calculate the sum before and after the transformation. So the tasks boil down to "maximize the sum of numbers by changing the numbers in them"
2) To maximize the sum, you need to maximize the terms. So you need to increase the numbers as much as possible, replacing one digit at a time.
3) How to increase the number as much as possible? It is necessary to replace the highest digit in the number with a nine, this will give the greatest effect.
4) The subtlety of times: if the highest digit is already a nine, we need the next digit, and so on. until we find NOT nine. If the number is one of nines, we ignore it.
5) Subtlety two: if we have the numbers 12 and 123, then a greater effect will be achieved by increasing the second, because He has more senior rank.
6) Subtlety three: if we have the numbers 123 and 456, then a greater effect will be achieved by increasing the first, because its most significant digit has a smaller value.
Hence the logic of the solution: for each number we are looking for the highest digit, not equal to 9. We fix information about the number, the digit number (ones, tens, hundreds, etc.), and the digit in the digit.
In the list of "candidates for replacement" found, we remove all options where the digit number is less than the maximum in the list (i.e. if someone can replace a hundred, then tens and ones are no longer considered). This step can be combined with list generation.
Of the remaining candidates, we are looking for the one with the smallest number in the category. This figure in this number is replaced by nine.
The increase in the number, and hence the increase in the total amount, will be equal to (9 - the old figure) * the weight of the discharge. For example, we replaced 2 by 9 in hundreds, we get an increase (9 - 2) * 100 = 700.
We repeat the process k times, we accumulate the increase.

Answer 2

Reread the condition slowly. Look at an example.
In the first problem, you need to choose some numbers, choose some digits in the numbers (no more than k digits in total) and replace them with other digits so that the sum increases as much as possible. Obviously, we need to replace the highest digits and always by 9. Therefore, we can immediately say that if we replace 3 digits in the number 128694, then this is "128" and we get 999694.
A special case here, if the number contains nines, they must be skipped.
Now the task is a little easier. It is necessary to distribute k digits by numbers in order to get the maximum profit, i.e. increase the maximum sum of numbers.
You can draw a little more tests on a piece of paper and understand that each number can be considered as a set of numbers. Each number is separate. For replacing one digit will increase the amount by (9-digit) * 10 ^ (digit digit) regardless of the remaining digits. Those. the task is still being transformed - there are a bunch of numbers, each with a known profit, if it is replaced. It is necessary to take no more than k of them, so that the sum of the change would be maximum.
Now it is clear that the problem is solved by sorting. Calculate the amount of profit for each digit, put it all into an array (maximum length 10 * n). Sort in descending order and take the sum of the first k values.
Votraya task - again slowly read. I can't understand for you. I can't explain it in a simpler way either. Try to draw tests as numbered dots, from which arrows go to the value a[i] - to whom they give gifts. You need to move exactly one arrow so that all the arrows close in one circle.
To solve it, you need to understand what will happen if you do not change a single number? The path from point 1 will either be a loop or something like the number "6". First, some kind of tail, which loops somewhere in the middle.
In the second case, it is clear what to do - you need to turn the last step back to the beginning of the tail, instead of the middle. If at the same time all the vertices are already in the path, then this is the answer.
The first case is more difficult. If the path already passes through all the vertices, then do nothing. If you change something, the cycle over all vertices will not work. If not all vertices are there, then the replacement should go to some non-included vertex, go around all of them and return to the cycle. Therefore, it is necessary to find the only vertex to which no arrow leads, make sure that the path from it passes all the vertices not included in the cycle and sticks into the cycle. And then it is necessary to expand the previous arrow before the point of sticking into the cycle to the beginning of the external path.

Answer 3

Something KIPPY calmed down, studying the answers)
Look, here is not quite a solution to the first problem, but rather an illustration to the explanations of Vindicar and 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}')