Problema
Sostituisci un numero con la somma dei fattoriali delle sue cifre: 145 dà 1! + 4! + 5! = 145, di nuovo lui, e 69 dà 6! + 9! = 363600. Ripetendo il procedimento si finisce sempre in un ciclo. La catena di un numero di partenza è formata dai suoi termini fino alla prima ripetizione: 69, 363600, 1454, 169, 363601 e poi di nuovo 1454, quindi 69 ha 5 termini distinti. Conta i numeri di partenza da 1 a limit la cui catena ha esattamente length termini distinti.
Implementa digit_factorial_chains(limit, length).
Molte catene passano per gli stessi numeri. Memorizza la lunghezza della catena di ogni numero appena la conosci e riutilizzala.
Input
limit: il numero di partenza più grande.
length: il numero di termini distinti richiesto, compreso quello di partenza.
Output
Restituisci quanti numeri di partenza n con 1 ≤ n ≤ limit hanno esattamente length termini distinti nella loro catena.
Vincoli
1 ≤ limit ≤ 100 000; 1 ≤ length ≤ 70
Esempi
Input:
limit = 2
length = 1
Output atteso:
expected = 2
Input:
long long limit = 2;
long long length = 1;
Output atteso:
long long expected = 2;
Input:
long limit = 2;
long length = 1;
Output atteso:
long expected = 2;
Spiegazione
1! = 1 e 2! = 2, quindi 1 e 2 portano ciascuno a se stesso e hanno una catena di 1 termine. La risposta è 2.
Input:
limit = 10
length = 2
Output atteso:
expected = 1
Input:
long long limit = 10;
long long length = 2;
Output atteso:
long long expected = 1;
Input:
long limit = 10;
long length = 2;
Output atteso:
long expected = 1;
Spiegazione
3 dà 6, poi 720, 5043, ..., quindi la sua catena è lunga. 10 dà 1! + 0! = 2 e poi di nuovo 2: due termini. Solo 10 ne ha esattamente 2, quindi la risposta è 1.
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Precalcola una volta sola i fattoriali da 0! a 9!.
Suggerimento 2
Registra il numero di passo di ogni valore nella catena corrente; una ripetizione ti dice dove inizia il ciclo.
Suggerimento 3
I valori nel ciclo hanno tutti la lunghezza del ciclo, e ogni valore prima del ciclo ha uno in più del successivo.
Complessità attesa
tempo O(limit × log limit) con la memoizzazione, spazio aggiuntivo O(limit)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.