Ciao a tutti.
Qualche mese fa avevo provato a risolvere il problema bloomsday, raggiungendo però solo 55 punti.
In questi giorni, vedendo quella barra piena a metà ho voluto riprovarci, portando a 75 punti il problema.
Ma ci sono 3 testcase (il numero 11, il 29 e il 30) che mi danno output non corretto.
La cosa strana è che in una soluzione precedentemente inviata gli ultimi due mi davano risultato corretto. Provando a riscaricare e ri-inviare quella stessa soluzione, però, me li ha dati errati
Penso di aver raggiunto la soluzione corretta del problema, e che fallisco i testcase per qualche problema di precisione nelle divisioni/potenze o per un qualche overflow con numeri molto grandi.
Dico questo perchè ho provato a confrontare la soluzione con quella ottenuta usando il metodo più “ingenuo” (calcolare i numeri e aggiungere via via le cifre) con E = K = 1, ho provato e tutti i primi 100 000 casi danno risultati uguali, (ho provato anche con numeri più grandi, ma ovviamente finisco domani a provare 10^18 numeri… il fatto è che appunto il caso 11 è nel subtask 3, dove E = K = 1, quindi mi sembra “strano” che dia il risultato sbagliato per via del metodo risolutivo
(Spiegazione della soluzione a cui sono arrivato)
In grande linee…
Con questa funzione mi ricavo l’ x più piccolo che mi fornisce un numero a c cifre:(ho iniziato a buttare long long a caso, sono disperato )
unsigned long long calcolacifra(long long c, long long K, long long E){
c–;
long double a =pow(10,c);
long double b=a/K;
b=pow(b,1/(long double)E);
return ceil(b)-1;
}
Ora, con i vari “x” (l’ x più piccolo con la cifra 1, con la cifra 2, ecc) posso calcolarmi la somma delle cifre (moltiplico la differenza tra l’x attuale e l’x precedente per il numero delle cifre correnti, penso si capisca.
Quando supero il valore N esco dal ciclo e tolgo l’ ultima “aggiunta” (per ovvi motivi) e per trovare il risultato finale mi trovo quante cifre mi mancano (N-sommaCifre) e lo divido per il numero di cifre correnti, sommandolo poi al valore dei vari x sommati.
Probabilmente la soluzione è più complicata di quello che dovrebbe essere.
Potrei anche condividere il codice, ma è una cosa bruttissima e farebbe sanguinare gli occhi a metà dei “lettori”
Nel frattempo grazie a tutti