Question

Помогите, пожалуйста, разобраться, как это решить. Буду благодарен, если на С++ или Python. "Даны n и m. Нужно найти минимальное число строго больше n с суммой цифр m.При том, что длина числа n <= 30000, m <= 270000."Из-за большой длины числа просто перебором найти ответ нельзя. Не знаю что делать.​

Answer 1

Это пока только тестовое, можешь проверить, код сырой

n,m = map(int, input().split())

n = str(n)

sum_num_n = sum([int(i) for i in n])

if sum_num_n < m:

   def count_num(x):

       if x/9 > x//9 :

           return x//9 + 1

       return x//9

   count = count_num(m)

   n += '0'*(count-len(n))

   n = list(n[::-1])

   i = 0

   nujno = m - sum_num_n

   while nujno!= 0:

       if nujno+int(n[i]) < 9:

           n[i] = str(int(n[i])+nujno)

           break

       else:

           nujno-=9-int(n[i])

           n[i] = '9'

       i+=1

   print(''.join(n[::-1]))

else:

   n = list(n[::-1])

   i = 0

   nujno = m - sum_num_n

   while True:

       if i == len(n)-1 :

           n.append('0')

       if n[i+1] == 9:

           continue

       else:

           n[i+1] = str(int(n[i+1])+1)

           nujno-=1

           if int(n[i])+nujno > 0:

               n[i] = str(int(n[i])+nujno)

               break

           else:

               nujno+=int(n[i])

               n[i] = '0'

       if nujno == 0:

           break

       i+=1

   print(''.join(n[::-1]))

   

Answer 2

Эта задача может быть решена с использованием динамического программирования. Мы можем создать двумерный массив, где dp[i][j] будет представлять минимальное число, состоящее из i цифр, с суммой цифр j.

Заведем массив dp размером (n+1) x (m+1). Начальные значения dp[0][0] и dp[1][1] будут равны 0, так как минимальное число суммой 0 является 0, а минимальное число с одной цифрой и суммой 1 - 1.

Затем мы можем заполнить массив dp по следующим правилам:

1. Для каждой пары (i, j), где i > 0 и j >= 0, мы можем рассмотреть все возможные цифры от 0 до 9, добавить каждую цифру к числу, состоящему из (i-1) цифры с суммой (j - этой цифры) и выбрать минимальное значение.

2. Если добавление цифры больше 9 приводит к сумме j больше m, мы не рассматриваем такие варианты.

3. Начиная с i = 2, мы рассматриваем только те значения j, которые можно достичь суммой двух цифр (j - digit) при условии, что dp[i-1][j-digit] уже было вычислено.

После заполнения массива dp, минимальное число с суммой m будет находиться в dp[n][m].

Вот пример кода на Python:

pythonCopy code
def find_min_number(n, m):
    dp = [[float('inf')] * (m+1) for _ in range(n+1)]
    dp[0][0] = 0

    for i in range(1, n+1):
        for j in range(1, m+1):
            for digit in range(10):
                if j - digit >= 0:
                    dp[i][j] = min(dp[i][j], dp[i-1][j-digit] * 10 + digit)

    return dp[n][m]

n = int(input("Введите n: "))
m = int(input("Введите m: "))

result = find_min_number(n, m)
print("Минимальное число с суммой", m, ":", result)

Этот код решит вашу задачу и найдет минимальное число с заданной суммой для больших значений n и m, используя динамическое программирование.