Статья Автор: Крюков Виктор

калькулятор одномерка

n = int(input())
dp = [10**9] * (n + 1)
prev = [-1] * (n + 1)
dp[1] = 0
for i in range(2, n + 1):
    dp[i] = dp[i-1] + 1
    prev[i] = i-1
    if i % 2 == 0 and dp[i//2] + 1 < dp[i]:
        dp[i] = dp[i//2] + 1
        prev[i] = i//2
    if i % 3 == 0 and dp[i//3] + 1 < dp[i]:
        dp[i] = dp[i//3] + 1
        prev[i] = i//3
path = []
cur = n
while cur != -1:
    path.append(cur)
    cur = prev[cur]
path.reverse()
s = ""
for i in range(1, len(path)):
    if path[i] == path[i-1] + 1:
        s+='1'
    elif path[i] == path[i-1] * 2:
        s+='2'
    elif path[i] == path[i-1] * 3:
        s+='3'
print(s)

Загрузка...

Чтобы оставить комментарий, необходимо авторизоваться

💬

Пока нет комментариев. Будьте первым!

Печать