Статья Автор: Лебедев Дмитрий Алексеевич

КЕГЭ_23_ДП на наборе команд

Постановка задачи (в достаточно общем виде):
Есть набор команд/правил, позволяющих получать из числа x другие числа.
Необходимо подсчитать число траекторий, переводящих число A в число B
На траектории возможно наложение ограничений:

длина траектории
запреты на некоторые позиции
необходимость содержать заданные точки
и т.п.

Для решения задач, возможно применение различных подходов

Динамическое программирование
Рекурсивное программирование
Методы линейной алгебры для исследования графов

Далее рассмотрим несколько задач и способы их решениия

Задача поиска всех решений.
Решение возможно, только если отсутствуют циклы к графе переходов (граф ациклический).
Это возможно всегда, если "система переходов" имеет "направление" (например используются команды + и *)
Стандартная постановка
Испольниетель Калькулятор умеет выполнять команды:

прибавлять натуральные числа из S (например 11 и 17)
умножать на числа из списка P - умножение возможно если результат строго больше аргумента.
(допускается умножение на вещественные числа с округлением до целого) Например (2 и 3)

Обозначим через t(x,y, k) - число траекторий, переводящих x в y за k команд (k = -1 будет обозначать, что на k ограничений нет)
Возможные задания:

Найдите количество траектокторий, переводящих число X в Y (t(X,Y,-1)
Для заданного X, найдите минимальное Y, такое что t(X,Y,-1) больше заданного N
Для заданного Y, найдите максимальное X, такое что t(X,Y,-1) больше заданного N
Для заданного отрезка [A;B] найдите "оптимальную" пару X, Y из отрезка, такую, что t(X,Y, -1) больше заданного N
"оптимальность" может быть по значению числа траекторий (минимальная) или по длине отрезка (максимальная)
Для заданного отрезка [A;B] найдите "оптимальную" пару X, Y из отрезка, такую, что t(X,Y, -1) меньше заданного N
"оптимальность" может быть по значению числа траекторий (максимальная) или по длине отрезка (минимальная)

Приведем конкретные задания и решения

Заадача 1.1
Команды
Прибавить 1001 или 1003 или 1007
Задание
Количество траекторий из 1 в 10_025
Способ решения
Динамическое программирование

def solve( ab, s, p): #программа реализована в общем виде (умножение с округлением вниз)
  a,b = ab
  dlt = b - a + 1
  M = [0] * dlt
  M[0] = 1 
  for i in range(dlt):
    z = M[i]
    if z == 0 : continue
    for x in s :
      if i + x < dlt : M[i + x] += z
    for x in p :
      y = int((a+i)*x)
      if y <= b : M[y - a] += z
  return M[-1]      
S = (1001, 1003, 1007)
P = []
A, B = 1, 10025
ans = solve((A,B),S,P)
print(f'Для наборов команд "+" = {S} "*" = {P}')
print(f'Количество траекторий из {A} в {B} равно {ans}')

Если есть команды прибавления, то количество траектрорий может быть ограмным или не быть совсем.
Поэтому интререснее задание, при котором надо для заданного A найти минимальное B, такое что количество траекторий больше заданного N
Попробуем решить такую задачу
S = [1001 ]
P = [2]
A = 1
N = 1_000_000
При такой формулировке использование массива для ДП становиться невозможным (до какого значения задавать список?)
или достаточно сложным (если есть хотя бы две команды прибавления, то можно оценить длину списка исходя только из этих команд)
Попробуем использовать словарь

def solve1( a, n, s, p): #программа реализована в общем виде (умножение с округлением вниз)
  M = {a:1}
  b = a - 1 
  while True :
    b += 1
    if not (b in M) : continue
    z = M[b]
    del M[b]
    if z >= n :
      print(f'{len(M)=}')
      return (b, z) 
    for x in s :
      if b + x in M :M[b + x] += z
      else : M[b + x] = z  
    for x in p :
      y = int(b*x)
      if y <= b : continue
      if y in  M : M[y] += z
      else : M[y] = z  
S = [9]
P = [12, 13]
A, N = 10_000, 100_000_000
ans = solve1(A,N,S,P)
print(f'Для наборов команд "+" = {S} "*" = {P} и {N}' )
print(f'Количество траекторий из {A} в {ans[0]} равно {ans[1] }')

Решение очень неэффективно, так как проверяет много промежуточных "пустых" значений
Это хорошо понятно, если используются только команды умножения
Например, если используются команды умножения га 2 и 3 и надо найти значение, при котором число траекторий больше 1_000_000
то ответом было бы число в районе 5*10⁸, хотя активных значений всего около 316
Это понятно, как если взять число N = 2^a*3^b , то число траекторий будет \(C_{a+b}^b\)
Проблема в том, что словарь в Python нельза переберать в порядке возрастания (в отличии от C++)
Для решений задания лучше применить C++ или изменить выбор следующего b
Приведем изменения на Python

def solve1( a, n, s, p): #программа реализована в общем виде (умножение с округлением вниз)
  M = {a:1}
  b = a - 1
  while True :
    b = min(M)
    z = M[b]
    del M[b]
    if z >= n :
      print(f'{len(M)=}')
      return (b, z) 
    for x in s :
      if b + x in M :M[b + x] += z
      else : M[b + x] = z  
    for x in p :
      y = int(b*x)
      if y <= b : continue
      if y in  M : M[y] += z
      else : M[y] = z  
S = [1]
P = [12, 13]
A, N = 10_000, 100_000_000
ans = solve1(A,N,S,P)
print(f'Для наборов команд "+" = {S} "*" = {P} и {N}' )
print(f'Количество траекторий из {A} в {ans[0]} равно {ans[1] }')

Способ отлично работает для команд умножения, но не подойдет для следующих параметро
Команды: +1, *2, *3
A =

import heapq
def solve1( a, n, s, p): #программа реализована в общем виде (умножение с округлением вниз)
  M = {a:1}
  Im = [a]
  
  while True :
    b = heapq.heappop(Im)
    z = M[b]
    del M[b]
    if z >= n :
      print(f'{len(Im)=} {len(M)=} {Im[0]}')
      return (b, z) 
    for x in s :
      if b + x in M : M[b + x] += z
      else :
        M[b + x] = z
        heapq.heappush(Im, b + x)
    for x in p :
      y = int(b*x)
      if y <= b : continue
      if y in  M : M[y] += z
      else :
        heapq.heappush(Im, y)
        M[y] = z 
    #'''
  return None,None
S = [9]
P = [12, 13]
A, N = 10_000, 100_000_000
ans = solve1(A,N,S,P)
print(f'Для наборов команд "+" = {S} "*" = {P} и {N}' )
print(f'Количество траекторий из {A} в {ans[0]} равно {ans[1] }')

import heapq
def solve1( a, n, s, p): #программа реализована в общем виде (умножение с округлением вниз)
  Im = [(a,1)]
  bb = a
  while True :
    zz = 0
    while Im:
      if Im[0][0] > bb : break
      b, z = heapq.heappop(Im)
      zz += z
    if zz >= n :
      print(f'{len(Im)=}')
      return (bb, zz)
    for x in p :
      y = int(bb * x)
      if y > bb : 
        heapq.heappush(Im, (y, zz))
    for x in s :
      heapq.heappush(Im, (bb + x, zz))
    bb = Im[0][0]  
  return None,None
S = [1]
P = [12, 13]
A, N = 100_000, 1_000_000
ans = solve1(A,N,S,P)
print(f'Для наборов команд "+" = {S} "*" = {P} и {N}' )
print(f'Количество траекторий из {A} в {ans[0]} равно {ans[1] }')

from collections import deque
def inic (s,p):
    dd={}
    for i in range(s):
        dd[i] = deque()
    for i in range(p):
        dd[100+i] = deque()
    return dd
def razgon(dd,sp,pp, a):
    k = 0
    for i in range(len(sp)):
        el,x = i, sp[i] + a[0]
        dd[el].append((x, a[1]))
            
    for i in range(len(pp)):
        el, y = 100+i, int(pp[i] * a[0])
        if y > a[0] : dd[el].append((y,a[1]))
            
    return True
def emin(dd):
    b = min([dd[el][0][0] for el in dd if dd[el]])
    z = sum([dd[el][0][1] for el in dd if dd[el] and dd[el][0][0]== b])
    for el in dd :
        if dd[el] and dd[el][0][0] == b :
            dd[el].popleft()
    return (b,z)
            
def solve(a,sp,pp,n):
    dd = inic(len(sp),len(pp))
    razgon(dd,sp,pp,(a,1))
    while True :
        bz = emin (dd)
        #print(f'{bz=}')
        if bz[1] >= n :
            return bz
        k = razgon(dd,sp,pp, bz)
        #(dd)
        #j = input('->')
    return None,None
s =[1]
p =[12,13]
a, n = 10_000, 1_000_000
ans =solve(a,s,p,n)
print(f'для команд "+"={s} и "*"={p}')
print(f'кол-во траекторий из {a} в {ans[0]} равно {ans[1]}')

def inic (s,p, a):
    dd, di, dz ={}, {}, {a: 1}
    for i in range(s):
        dd[i] = []
        di[i] = 0
    for i in range(p):
        dd[100+i] = []
        di[100+i] = 0
    return dd, di, dz
def razgon(dd, dz, sp,pp, a):
    k = 0
    for i in range(len(sp)):
        el,x = i, sp[i] + a
        dd[el].append(x)
        if x in dz : dz[x] += dz[a]
        else : dz[x] = dz[a]
    for i in range(len(pp)):
        el, y = 100+i, int(pp[i] * a)
        if y > a :
            dd[el].append(y)
            if y in dz : dz[y] += dz[a]
            else : dz[y] = dz[a]
    return True
def emin(dd, di):
    b = min([dd[el][di[el]] for el in dd])
    for el in dd :
        if dd[el][di[el]] == b :
            di[el] += 1
            #if di[el] > 1000000:
            #    dd[el] = dd[el][di[el]:]
            #    di[el] =0
    return b
            
def solve(a,sp,pp,n):
    dd, di, dz = inic(len(sp),len(pp), a)
    razgon(dd,dz,sp,pp,a)
    #print(f'{dd}\n{di}\n{dz}')
    while True :
        b = emin (dd, di)
        z = dz[b] 
        #print(f'{b=} {z=}')
        if z >= n :
            return b, z
        k = razgon(dd,dz, sp, pp, b)
        #print(f'{dd}\n{di}\n{dz}')
        #j = input('->')
    return None,None
t0 =prt()
s =[1]
p =[12,13]
a, n = 10_000, 1_000_000
ans =solve(a,s,p,n)
print(f'для команд "+"={s} и "*"={p}')
print(f'кол-во траекторий из {a} в {ans[0]} равно {ans[1]}')

Печать