Sto risolvendo questo problema, ma non riesco ad andare oltre gli 80/100!
E’ semplice, ma non so dove sbaglio o cosa mi sfugga.
La mia idea è quella di “contare” quante coppie di numeri non posso capitare insieme. Una volta stabilito questo numero (che io ho chiamato “ric”), il risultato sarà dato da N-ric.
Il codice della procedura risolutiva è questo:
int solve(){
if(k==1)
return 0;
if(N==1)
return 1;
sort(a, a+N);
int ric = 0;
for(int i=0, prev=1; i<N; i++)
for(int j=prev, val = a[i]*k; j<N; j++)
if(val <= a[j]){
prev=j;
if(val==a[j]){
ric++;
prev++;
}
break;
}
return N-ric;
}
“prev” è l’indice dal quale la volta dopo il ciclo dovrà partire. Infatti l’array è ordinato in ordine crescente ed ogni elemento è univoco, perciò una volta trovato un valore minore o uguale di a[i]*k bisognerà partire da quello (se è minore) o da quello successivo (se l’abbiamo trovato).
Sto sbagliando a fissarmi troppo su questo algoritmo oppure anche qualcun altro l’ha risolto in questo modo?