Aiuto problema: dream (o meglio: nigthmare 🤣 )

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.

Qualcuno ha qualche consiglio su come migliorare?

Provo a darti qualche consiglio per come l’ho risolto io:

  1. il numero di cifre del numero palindromo è pari, diventa facile calcolare prima una metà e poi l’altra
  2. 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à
  3. 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
1 Mi Piace

Scusa, ho provato a ragionarci, ma non capisco bene il punto 2 cosa significa, se potessi spiegarti meglio te ne sarei grato.

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).

Il terzo punto non lo si risolve sommando al numero n con X cifre: 11 * ( 10 ^ X/2 -1 ) ?

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.

Se lo divido a metà è semplicemente un numero crescente che poi sarà specchiato nell’altra metà

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