Ho sottoposto la mia soluzione di quadrati perfetti alla piattaforma, ma il mio programma passa solo per i task di esempio, negli altri casi ottengo output incorretti.
Non capisco dove sbaglio!!..eppure mi sembra di aver colto l’inghippo del problema che è quello di dichiarare le variabili di tipo double visto che a e b<10^18…ma ottengo sempre output non corretto…
Nella mia soluzione eseguo un ciclo che parte da a e arriva a b o si blocca prima se trovo un quadrato che supera b.
La prima osservazione da fare è che si può restringere la ricerca nell’insieme [ sqrt(a), sqrt(b) ] riducendo il problema da un ordine di 10^18 ad un ordine di 10^9.
Per quanto riguarda le variabili prova ad usare i Long Long al posto dei Double.
Sono riuscito a risolvere grazie al tuo ragionamento, Luca, però dopo aver guardato la soluzione nel booklet ho visto che è diversa.
Nella soluzione parla di ricerca binaria mentre io ho semplicemente usato una formula (quindi complessità O(1)).
Questo è il codice
long long a = ceil(sqrt(A));
long long b = floor(sqrt(B));
int conto = b-a+1;
Sono stato fortunato a passare i casi di esempio oppure la mia soluzione è giusta?
Ciò che faccio io è calcolare quanti numeri ci sono tra sqrt(a) e sqrt(b), dato che ognuno elevato al quadrato sarà sicuramente compreso tra a^2 e b^2
In effetti sì, poteva aver senso aggiungere anche la tua soluzione al booklet
Tuttavia tieni conto che il fatto che l’algoritmo usi semplicemente una formula non significa automaticamente che abbia complessità O(1). Ad esempio nella formula utilizzi sqrt che internamente fa delle operazioni per calcolare la radice quadrata. Un’implementazione “naive” di sqrt farebbe uso di una ricerca binaria (anche se l’implementazione fatta dalla libreria standard è molto più furba)…
