import sys
sys.stdin = open('input.txt')
sys.stdout = open('output.txt', 'w')
def solve(t):
n, m = map(int, input().strip().split())
ans = 0
def dfs(i, num):
nonlocal ans
ans = max(ans, num%m)
if i>=n:
return
if 3 != num%10:
dfs(i + 1, 10 * num+3)
if 6 != num % 10:
dfs(i + 1, 10 * num + 6)
if 9 != num % 10:
dfs(i + 1, 10 * num + 9)
dfs(0, 0)
return ans
T = int(input().strip())
for t in range(1, T + 1):
res = solve(t)
if t<T:
print(res, end =" ")
else:
print(res, end="")
Qualcuno potrebbe aiutarmi a capire come potrei migliorare il codice?
ciao, nel problema cabala ci sono più test cases, quindi ogni volta ricalcoli inutilmente molti numeri. quello che puoi fare è calcolarteli una sola volta all’inizio salvandoli per poi utilizzarli quando ti servono
Ho provato a seguire il tuo consiglio, tuttavia è ancora lento.
import sys
sys.stdin = open('input.txt')
sys.stdout = open('output.txt', 'w')
def solve():
n, m = map(int, input().strip().split())
already = set()
ans = 0
def dfs(i, num, last_add):
nonlocal ans
ans = max(ans, num)
if i >= n or num in already:
return
already.add(num)
if 3 != last_add:
dfs(i + 1, (10 * num+3) % m, 3)
if 6 != last_add:
dfs(i + 1, (10 * num + 6) % m, 6)
if 9 != last_add:
dfs(i + 1, (10 * num + 9) % m, 9)
dfs(0, 0, 0)
return ans
T = int(input().strip())
for j in range(1, T + 1):
res = solve()
if j < T:
print(res, end=" ")
else:
print(res, end="")
non è proprio quello che intendevo. come puoi vedere chiami la funzione solve T volte. non c’è forse un modo per chiamarla solo una volta avendo comunque tutti i numeri?
puoi usare una matrice che ti vai a riempire all’inizio con i numeri validi che ha come indice di riga il numero di cifre di un numero, e poi per ogni test case non ti serve altro che scorrere la matrice in base a quante cifre ti servono
Non sono troppo sicuro che questo aiuti. Del resto nel testcase
50
18 10000000
18 20000000
...
comunque dovresti scorrere tutti i numeri ogni volta (tra l’altro facendo moduli diversi), che alla fine non è molto diverso da fare la ricorsione ogni volta.
Ok… non so se sia solo dovuto all’assenza di test forti o se ci sia qualche ragione a me ignota per cui va così veloce. Potresti mandarmi il codice (possibilmente con un messaggio privato) così posso testarlo in locale sul test di cui sopra?