Advertisement
Guest User

Untitled

a guest
Jul 19th, 2023
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.03 KB | None | 0 0
  1. MAXSIZE = 60
  2.  
  3. dp = [[0] * MAXSIZE for _ in range(11)]
  4. dp[0] = [1] * MAXSIZE
  5. for i in range(1, 11):
  6.     for j in range(MAXSIZE):
  7.         dp[i][j] = sum(dp[i - 1][j:])
  8. for i in range(1, 11):
  9.     for j in range(MAXSIZE):
  10.         dp[i][j] += dp[i - 1][j]
  11.  
  12. dp[0] = [0] * MAXSIZE
  13. for x in dp:
  14.     x += [1]
  15.  
  16.  
  17. # print(*dp, sep="\n")
  18.  
  19.  
  20. def get_number(N):
  21.     ANSWER_LENGTH = 1
  22.     while dp[9][-ANSWER_LENGTH - 1] < N:
  23.         ANSWER_LENGTH += 1
  24.  
  25.     prev_digit = 0
  26.     for i in range(-ANSWER_LENGTH, 0):
  27.         for new_prev_digit in range(9, prev_digit - 1, -1):
  28.             value = N - sum(dp[9 - x][i] for x in range(new_prev_digit)) + sum(dp[9 - x][i] for x in range(prev_digit))
  29.             if value > 0:
  30.                 print(new_prev_digit, end="")
  31.                 prev_digit = new_prev_digit
  32.                 N = value
  33.                 break
  34.     print()
  35.  
  36.  
  37. # for n, ANSWER_LENGTH in [(3, 1), (14, 2), (215, 3)]:  # 3, 14, 789
  38. #     get_number(n)
  39. n = int(input())
  40. if n < 10:
  41.     print(n)
  42. else:
  43.     get_number(n + 1)
  44.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement