Digprime.py — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
 
(не показано 6 промежуточных версий этого же участника)
Строка 1: Строка 1:
 
<source lang="python">
 
<source lang="python">
# globals
 
 
import sys
 
import sys
  
 +
digits = 19
 +
# globals
 
input_str = ""
 
input_str = ""
dp = [[[-1, -1], [-1, -1]] for i in range(25)]
+
dp = [[[-1, -1], [-1, -1]] for i in range(digits)]
 +
N = None
 
   
 
   
  
Строка 16: Строка 18:
 
next(tc_)
 
next(tc_)
  
digits = 19
 
 
p10 = [10**i for i in range(digits)]
 
p10 = [10**i for i in range(digits)]
  
Строка 28: Строка 29:
 
     global input_str
 
     global input_str
 
     global dp
 
     global dp
     if i == len(input_str):
+
     global N
        return taken
+
    if dp[i][taken][ls] != -1:
+
        return int(dp[i][taken][ls])
+
 
+
    if ls and taken:
+
        return p10[len(input_str) - i]
+
  
 
     res = 0
 
     res = 0
Строка 41: Строка 36:
 
     else:
 
     else:
 
         limit = int(input_str[i])
 
         limit = int(input_str[i])
 +
 
     for x in range(limit + 1):
 
     for x in range(limit + 1):
         res += calculate(i + 1, taken | (x == 2) | (x == 3) | (x == 5) | (x == 7), ls | (x != limit))
+
         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] = int(res)
+
     dp[i][taken][ls] = res
     return int(res)
+
     return res
 
   
 
   
 
   
 
   
 
for input_str in tc_:
 
for input_str in tc_:
     for j in range(25):
+
    N = len(input_str)
 +
     for j in range(digits):
 
         dp[j][0][0] = -1
 
         dp[j][0][0] = -1
 
         dp[j][1][0] = -1
 
         dp[j][1][0] = -1

Текущая версия на 02:33, 1 мая 2022

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))