27/01/13 23:51
Maury91
Questo è il codice che ho usato, purtroppo nella versione ottimizzata risulta avvolte instabile non son riuscito a capire come risolvere questa rara instabilità...
#include <stdio.h>
#include <stdlib.h>
typedef struct findmin_t {
int num;
struct findmin_t* prev;
struct findmin_t* next;
struct findmin_t* next_del;
int exist;
} findmin;
findmin *min,*f_del;
void insert_order(findmin *ins,findmin *start) {
findmin *s;
//Inserimento ordinato.. è quello che rallenta il codice,
//ottimizzando questo il codice può diventare velocissimo...
if (start!=NULL)
s=start;
else
s=min;
if (ins->num<=s->num) {
s->prev=ins;
ins->next=s;
min=ins;
} else {
while((s->num<ins->num)&&(s->next!=NULL)) {
s=s->next;
}
if (s->num<ins->num) {
s->next=ins;
ins->prev=s;
ins->next=NULL;
} else {
ins->prev=s->prev;
s->prev->next=ins;
ins->next=s;
s->prev=ins;
}
}
}
long int testcase(long int a,long int b, long int c, long int r, long int n, long int k) {
long int s[k+1],i,now;
findmin *exit=NULL,*l_del,*l_min=NULL,*sup,*l_ins,*ff;
int l;
//Preveniamo errori
if (k<2) return 0;
s[0]=a;
min = (findmin*)malloc(sizeof(findmin));
min->num=a;
min->prev=NULL;
min->next=NULL;
min->next_del=NULL;
f_del=l_ins=min;
for(i=1;i<k;i++)
{
long long int tmp1=b%r;
long long int tmp2=s[i-1]%r;
long long int ltmp=tmp1*tmp2;
ltmp=ltmp%r;
long long int tmp3=ltmp;
long long int tmp4=c%r;
long long int final=(tmp3+tmp4)%r;
s[i]=final;
sup=(findmin*)malloc(sizeof(findmin));
sup->num=s[i];
sup->exist = 1;
l_ins->next_del=sup;
insert_order(sup,NULL);
l_ins=sup;
}
l=k;
for (i=k;i<n;i++) {
now=0;
if (min->num==0) {
if (l_min==NULL)
sup=min;
else {
//Scelgo il punto di partenza più conveniente
if (exit->num<l_min->num) {
if (l_ins->num<exit->num) {
now = l_ins->num;
sup = l_ins;
}
else {
now = exit->num;
sup = exit;
}
}
else{
if (l_ins->num<l_min->num) {
now = l_ins->num;
sup = l_ins;
}else {
now = l_min->num;
sup = l_min;
}
}
//Torno indietro di uno se possibile
if (sup->prev!=NULL)
sup = sup->prev;
}
//Cerco quello immediatamente successivo nella lista
while((sup->next!=NULL)&&(now>=sup->num)) {
if (now==sup->num)
now++;
else {
sup=sup->next;
}
}
//Se sono alla fine della lista e quindi son uscito perché è l'ultimo elemento, incremento now
if (sup->num==now)
now++;
//Mi salvo qual'è l'ultimo trovato
l_min=sup;
}
//Eliminazione
if (f_del->prev!=NULL) {
f_del->prev->next = f_del->next;
f_del->exist = 0;
} else
min=f_del->next;
if (f_del->next!=NULL)
f_del->next->prev = f_del->prev;
if (exit!=NULL)
free(exit);
//Salvo l'ultimo elemento uscito (molto utile a fini statistici)
exit=f_del;
f_del=f_del->next_del;
//Creo un nuovo elemento
sup=(findmin*)malloc(sizeof(findmin));
sup->num=now;
sup->exist = 1;
l_ins->next_del=sup;
//Capita qualche volta che si corrompa il risultato
//Mettendo come commento da qui fino all'else il risultato sarà sicuramente corretto!
if (l_min!=NULL) {
ff=l_min->prev;
if (!ff->exist)
ff = min;
while (!ff->exist) {
ff = ff->prev;
if (ff==NULL)
ff=min;
}
insert_order(sup,ff);
}
else
insert_order(sup,NULL);
l_ins=sup;
//Salvataggio nella matrice (ora inutilizzata)
s[i%(k+1)]=now;
if (i==k*2) return s[(n-1)%(k+1)];
}
return now;
}
int main() {
FILE *f,*f2;
int cont,i;
long int n,k,a,b,c,r;
f = fopen("input.txt","r");
f2 = fopen("output.txt","w");
fscanf(f,"%d",&cont);
for (i=0;i<cont;i++) {
fscanf(f,"%d %d",&n,&k);
fscanf(f,"%d %d %d %d",&a,&b,&c,&r);
printf("Case #%d : %d\n",i+1,testcase(a,b,c,r,n,k));
}
fclose(f);
fclose(f2);
return 0;
}
Ultima modifica effettuata da Maury91 28/01/13 14:42
aaa
