Cabala Python (70/100)

Aiuto
1 
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?

2

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
3

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

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

5

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

6

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.

7

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

8

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?