Bloomsday problema su 3 testcase

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 :confounded:

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 :zipper_mouth_face:)

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

Ciao, senza vedere il codice è piuttosto difficile capire qual è l’errore, comunque trattandosi di quei testcase potrei azzardare che si tratti di overflow o di un problema di precisione.

2 Mi Piace

Ecco qui il codice… probabilmente è più complicato di quel che serve… ma dettagli

https://pastebin.com/MgZSy7XS

Prova con questo input: 1 3 29

2 Mi Piace

Mi dà 11, che è giusto
La sequenza di numeri generati è
1 8 27 64 125 216 343 512 729 1000 1331
L’ ultima cifra è l’ ultimo “1” di 1331, alla posizione 11, no?

È giusto, tuttavia testando in locale il tuo codice ottengo 12. Su ideone ottengo lo stesso risultato. Che compilatore usi?

2 Mi Piace

Uso il compilatore mingw32-g++.exe