Dopo il primo round delle OIS stavo tentando di ottenere qualche punto in più su palindromic dreams visto che sono bloccato a 35 punti.
La mia idea è abbastanza semplice parto da: 10 ^ (X/2-1), aggiungo a questo numero una quantità i a partire da 0 fino a K-1 e ogni volta lo duplico, lo inverto e concateno l’originale e l’inverso, e infine aggiungo il risultato alla somma totale.
Ovviamente così la gestione con numeri di cifre molto grandi è complessa; allora avevo provato un’altra soluzione usando una classe tipo BigInt di Java e cioè facendo tutte le operazioni su numeri rappresentati sottoforma di stringhe e in questo modo riesce a gestire anche i casi con numeri di cifre grandi ma solo in locale perché sulla piattaforma risulta 0 punti.
Provo a darti qualche consiglio per come l’ho risolto io:
il numero di cifre del numero palindromo è pari, diventa facile calcolare prima una metà e poi l’altra
tutti i numeri palindromi con X cifre sono almeno uguali a una certa quantità, il modulo di questa quantità lo puoi già calcolare in anticipo con K e dopo ti rimane da calcolare solo la differenza tra ogni numero e questa quantità
la successione dei numeri palindromi con cifre pari è abbastanza semplice, se riesci a capire il modo in cui incrementano hai già risolto gran parte del problema
per capire come mettere in atto il punto 2 devi essere sicuro di aver capito il punto 3 (cioè devi essere in grado, dato un numero palindromo a X cifre, di capire il numero palindromo successivo).
questa formula cosa dovrebbe dare come risultato? se per esempio mettiamo X=4 il risultato della tua espressione diventa 11*99 = 1089 che non è un numero palindromo
No se tipo il numero palindromo n = 102201, allora k sarà 6, quindi la mia formula sarà 11 * ( 10²) = 1100, 102201 + 1100 = 103301 che è il prossimo numero palindromo
secondo il tuo ragionamento per trovare il numero palindromo successivo a 1991 dovrei aggiungere 110 il che da come risultato 2101.
Comunque non devi cercare di trovare la formula, ma il modo in cui si susseguono, se dividi il numero in due metà ti sarà più chiaro.
Esatto, quindi ora sai calcolare facilmente ogni numero palindromo successivo ad un altro. Però c’è il problema che questi numeri possono avere fino a 100k cifre, ora prova a seguire questo consiglio che ti permette di calcolare il modulo di ogni numero palindromo:
In questo modo alla fine dividi il calcolo del numero palindromo in 3 parti
Ti assicuro che ci sto provando a capire, ma proprio non arrivo a comprendere cosa significhi che tutti i numeri palindromi con ‘X’ cifre sono almeno uguali a una certa quantità, io avevo pensato significasse che la somma di tutti i numeri palindromi che hanno X cifre valesse N ma non so se è giusto.
Prendi in considerazione l’esempio:
i 3 numeri palindromi hanno tutti in comune 1001, il primo è 1001 +0, il secondo è 1001 + 110 e il terzo è 1001+220 quindi la soluzione è 3*1001+ 110+220=3003+330=3333.
Almeno ho interpretato così il suggerimento e ha funzionato.