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

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

Сначала заполним dp[1][j] для всех возможных значений j от 0 до 9. Эти значения будут равны j, так как минимальное однозначное число с суммой цифр j - это само число j.

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

dp[i][j] = min(dp[i-1][k] * 10 + j - k) для всех k от 0 до 9, где k < j и (i-1 >= k)

Это означает, что мы берем минимальное число длины (i-1) с суммой цифр k и добавляем к нему цифру j - k, чтобы получить число длины i с суммой цифр j. Затем мы выбираем минимальное из всех таких возможных чисел.

Наконец, после заполнения массива dp, мы ищем минимальное число длины n с суммой цифр m, которое больше n. Мы начнем с n+1 и будем проверять значения dp[n+1][m], dp[n+2][m], и так далее, пока не найдем подходящее число.

Вот пример решения на Python:

pythonCopy code
def find_min_number(n, m):
    dp = [[float('inf')] * (m + 1) for _ in range(n + 1)]
    
    for j in range(10):
        if j <= m:
            dp[1][j] = j
    
    for i in range(2, n + 1):
        for j in range(1, m + 1):
            for k in range(10):
                if k < j and i - 1 >= k:
                    dp[i][j] = min(dp[i][j], dp[i - 1][k] * 10 + j - k)
    
    for i in range(n + 1, 10**6):
        if dp[n + 1][m] <= i:
            return i

n = 30000
m = 270000
result = find_min_number(n, m)
print(result)

Этот код создает массив dp и заполняет его, а затем ищет минимальное число, удовлетворяющее условиям задачи.