Cabala Python (70/100)

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

1 Mi Piace

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

L’aggiunta che hai fatto probabilmente peggiora il tempo di esecuzione ma non è importante. Comunque ti sconsiglio fortemente il python, perché può essere fino a ordini di grandezza più lento del C++ (in particolare questa soluzione dovrebbe passare in C++).
Tra l’altro il checker non si lamenta se trova trailing spaces alla fine dell’output in teoria quindi puoi tranquillamente stampare sempre uno spazio dopo il numero

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.

non saprei di preciso, comunque utilizzando ciò che ho scritto sopra nel test case più lento impiega 0.058s

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?