Ciao a tutti, sto cercando di risolvere il problema “salta” delle nazionali 2011. Il mio programma produce un output corretto, tuttavia supera il limite di un secondo negli ultimi due testcase. Qualcuno saprebbe indicarmi un modo per ottimizzarlo? Oppure un algoritmo più efficiente?
Ecco il mio codice:
#include <stdio.h>
#include <stdlib.h>
unsigned int N,i,t;
unsigned int im=0;
unsigned int vettore[1000000];
unsigned int var[1000000];
unsigned int indici[1000000];
int main()
{
FILE *in;
in = fopen("input.txt","r");
fscanf(in,"%d",&N);
for(i=1;i<=N;i++){
fscanf(in,"%d",&vettore[i]);
}
i=1; var[1]=1;
indici[1]=1;
for(t=2;t<=N;t++){
indici[t]=((i+vettore[i])%N)+1;
i=indici[t];
var[i]=1;
}
t--;
im=t;
for(i=1;i<=t;i++){im=im-var[i];}
FILE *out;
out = fopen("output.txt","w");
fprintf(out,"%d\n",im);
for(i=1;i<=t;i++){
if(var[i]==0){
fprintf(out,"%d ",i);
}
}
return 0;
}
Immagina di raggiungere la posizione X, segnarla come visitata e riprendere i “salti”.
Se dopo alcuni salti ricapiti in X, cosa puoi concludere?
Grazie mille, sono riuscito a semplificare notevolmente l’algoritmo, tuttavia il tempo di esecuzione per l’ultimo testcase è sempre superiore ad un secondo. Come posso guadagnare altro tempo?
Ecco il nuovo codice:
#include <stdio.h>
#include <stdlib.h>
unsigned int N,i,t;
unsigned int im=0;
unsigned int vettore[1000000];
unsigned int var[1000000];
unsigned int indici[1000000];
int main()
{
FILE *in;
in = fopen("input.txt","r");
fscanf(in,"%d",&N);
for(i=1;i<=N;i++){
fscanf(in,"%d",&vettore[i]);
}
i=1; var[1]=1;
indici[1]=1;
for(t=2;t<=N;t++){
indici[t]=((i+vettore[i])%N)+1;
i=indici[t];
if(var[i]==1){break;}
var[i]=1;
}
im=N-t+1;
FILE *out;
out = fopen("output.txt","w");
fprintf(out,"%d\n",im);
for(i=1;i<=N;i++){
if(var[i]==0){
fprintf(out,"%d ",i);
}
}
return 0;
}
Prova a togliere l’array “indici” che tanto non ti serve a niente 
Comunque è strano che vada fuori tempo, è O(N) con un N non così grande…
Ora funziona, ho dovuto dichiarare locali le variabili che avevo messo globali. Grazie mille per l’aiuto!
