Статья Автор: Корнеев Александр

ср

дз2-2
n = int(input())
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
    res = dp[i - 1]    
    if i > 7:
        res = min(res, dp[i - 7])        
    if i % 2 == 0:
        res = min(res, dp[i // 2])        
    dp[i] = res + 1
print(dp[n])

дз2-3
n = int(input())
dp = [float('inf')] * (n + 1)
parent = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
    if dp[i - 1] < dp[i]:
        dp[i] = dp[i - 1]
        parent[i] = i - 1        
    if i > 7 and dp[i - 7] < dp[i]:
        dp[i] = dp[i - 7]
        parent[i] = i - 7        
    if i % 2 == 0 and dp[i // 2] < dp[i]:
        dp[i] = dp[i // 2]
        parent[i] = i // 2        
    dp[i] += 1
path = []
curr = n
while curr != 0:
    path.append(curr)
    curr = parent[curr]
path.reverse()
print(dp[n])
print(*(path))

дз3-1
import sys
input_data = sys.stdin.read().split()
if input_data:
    n = int(input_data[0])
    MOD = 10**9 + 7
    dp = [0] * (n + 1)
    dp[0] = 1
    for i in range(n + 1):
        if dp[i] > 0:
            current_ways = dp[i]
            if i + 1 <= n:
                dp[i + 1] = (dp[i + 1] + current_ways) % MOD
            if i + 5 <= n:
                dp[i + 5] = (dp[i + 5] + current_ways) % MOD
            if i > 0 and i * 2 <= n:
                dp[i * 2] = (dp[i * 2] + current_ways) % MOD
    print(dp[n])

дз3-2
import sys
n = int(sys.stdin.read().strip())
dp = [0] * (n + 1)
for i in range(1, n + 1):
    min_steps = dp[i - 1] + 1    
    if i >= 5:
        min_steps = min(min_steps, dp[i - 5] + 1)
    if i % 2 == 0:
        min_steps = min(min_steps, dp[i // 2] + 1)        
    dp[i] = min_steps
print(dp[n])

дз3-3
import sys
n = int(sys.stdin.read().strip())
dp = [0] * (n + 1)
parent = [None] * (n + 1)
for i in range(1, n + 1):
    min_steps = dp[i - 1] + 1
    best_parent = (i - 1, 1)
    if i >= 5 and dp[i - 5] + 1 < min_steps:
        min_steps = dp[i - 5] + 1
        best_parent = (i - 5, 2)
    if i % 2 == 0 and dp[i // 2] + 1 < min_steps:
        min_steps = dp[i // 2] + 1
        best_parent = (i // 2, 3)
        
    dp[i] = min_steps
    parent[i] = best_parent
path = []
curr = n
while curr > 0:
    prev_node, spell = parent[curr]
    path.append(spell)
    curr = prev_node
path.reverse()
print(dp[n])
if dp[n] > 0:
    print(*(path))
else:
    print()

дз2-1
import sys
n = int(sys.stdin.read().strip())
MOD = 10**9 + 7
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
    prev_numbers = set()
    prev_numbers.add(i - 1)
    if i - 7 >= 1:
        prev_numbers.add(i - 7)
    if i % 2 == 0:
        prev_numbers.add(i // 2)
    total = 0
    for prev in prev_numbers:
        total = (total + dp[prev]) % MOD
        
    dp[i] = total
print(dp[n])

Загрузка...

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

💬

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

Печать