Python-оптимизация алгоритма динамического программирования из codechef
Материал из DISCOPAL
StasFomin (обсуждение | вклад) (Новая страница: «При разборе ваших решений, столкнулся с [[:Участник:Hakob/prime-digits|одной из попыток], с результ…») |
(нет различий)
|
Версия 23:38, 30 апреля 2022
При разборе ваших решений, столкнулся с [[Участник:Hakob/prime-digits|одной из попыток], с результатом «вроде все сделано правильно, но система не пропускает, наверно что-то не так с системой или вообще питон не потянет, вот на плюсах все решают и все хорошо».
Попробую кратко показать, как можно системно поработать с улучшением решения, даже не особо вьезжая в алгоритм (ну при условии, что идея будет правильна).
import sys digits = 19 # globals input_str = "" dp = [[[-1, -1], [-1, -1]] for i in range(digits)] N = None def get_input(): lines = sys.stdin.readlines() content = " ".join(lines).strip() for token in content.split(): yield token tc_ = get_input() next(tc_) p10 = [10**i for i in range(digits)] def calculate(i, taken: int, ls: int) -> int: ''' i — индекс цифры taken — встречали ли простые цифры раньше ls — в текущем индексе можно делать полный перебор ''' global input_str global dp global N res = 0 if ls: limit = 9 else: limit = int(input_str[i]) for x in range(limit + 1): newtaken = taken or (x == 2) or (x == 3) or (x == 5) or (x == 7) newls = ls or (x != limit) newi = i + 1 if newi == N: ret = newtaken elif newls and newtaken: ret = p10[N - newi] else: cached = dp[newi][newtaken][newls] if cached != -1: ret = cached else: ret = calculate(newi, newtaken, newls) res += ret dp[i][taken][ls] = res return res for input_str in tc_: N = len(input_str) for j in range(digits): dp[j][0][0] = -1 dp[j][1][0] = -1 dp[j][1][1] = -1 dp[j][0][1] = -1 print(calculate(0, 0, 0))