Imprimă pagina - usaco training ..sectiunea 1.4 .. checker challenge

Titlul: usaco training ..sectiunea 1.4 .. checker challenge
Scris de: tudor george cristian din Septembrie 14, 2005, 19:25:17

imi explica si mie cineva cum pot sa fac sa-mi intre ultimul test (n=13) in limita de o secunda ? .... mie imi da 1.21 s ...

Titlul: usaco training ..sectiunea 1.4 .. checker challenge
Scris de: VladS din Septembrie 14, 2005, 19:30:23

Probabil ca atunci s-a oprit executia. La tine pentru n=13 in cat timp iti ruleaza?
Btw, ai implementat cu simetrizare?

Titlul: usaco training ..sectiunea 1.4 .. checker challenge
Scris de: tudor george cristian din Septembrie 14, 2005, 19:38:07

da....am folosit simetrizare .... pe calc meu ...la n=13 ...imi da timpul 0.44 s ... iar pe usaco imi da mai mult de o sec ....

Titlul: usaco training ..sectiunea 1.4 .. checker challenge
Scris de: VladS din Septembrie 14, 2005, 19:54:34

Daca ai folosit toate hinturile inseamna ca implementarea ta nu este cea mai buna. Poti sa pui unele functii inline, variabile constante (daca nu faci asta deja). Daca nici asa nu merge incearca sa faci iterativ. Asta ar trebui sa fie suficient. Mai sunt unele optimizari super da te las sa le afli din Analysis. :)

Titlul: usaco training ..sectiunea 1.4 .. checker challenge
Scris de: tudor george cristian din Septembrie 14, 2005, 23:51:17

e de-a dreptul enervant... chiar nu-mi dau seama ce as putea sa ii fac ca sa mearga ...

Titlul: usaco training ..sectiunea 1.4 .. checker challenge
Scris de: tudor george cristian din Septembrie 18, 2005, 00:23:34

eu tot nu am reusit sa o bag sub o secunda ... am facut-o si iterativ si tot imi da un timp de 1.3 secunde .... sugestii cineva ?

Cod:


void back()
 {
  FILE *g=fopen("checker.out","w"),
       *f=fopen("checker.in","r");
  unsigned long m=0;
  int k=1,as,gasite=0,aux,n,limita;
  fscanf(f,"%d",&n);
  fclose(f);
  if(n>6)  aux=(n+1)/2;
  else aux=n;
  
  st[k]=val1;
  while(k>val1)
   {
    limita=n;
    if(k==1 || (k==2 && st[1]==7)) limita=aux; 
    do{
       if(st[k]<limita) {st[k]++;as=1;}
       else as=val1; 

       }while((as) && (diag[st[k]-k+n]!=val1 || diag2[k+st[k]]!=val1 || coloana[st[k]]!=val1));
    if(as) {
           diag[st[k]-k+n]=diag2[st[k]+k]=coloana[st[k]]=1;  
           if(k==n) {
                     //   noteaza();
                     if((st[1]!=aux && n>6) || (st[1]==aux && n%2==val1 && n>6) || (n==13)) m+=2;
                     else m++;
                     if(gasite<3)
                     { for(int j=1;j<=n;j++) {fprintf(g,"%d",st[j]);if(j!=n) fprintf(g," ");}
                       fprintf(g,"\n");gasite++; 
                     }  
                     coloana[st[k]]=diag[st[k]-k+n]=diag2[st[k]+k]=val1;
                       } 
                      else {k++;st[k]=val1;}
                   }
    else {k--;coloana[st[k]]=diag[st[k]-k+n]=diag2[st[k]+k]=val1;}
    }
    fprintf(g,"%ld\n",m);
    fclose(g); 
 
   }

Editat de moderator: Invatati sa puneti "[code]" inaintea unui fragment de cod

Titlul: usaco training ..sectiunea 1.4 .. checker challenge
Scris de: Cosmin Negruseri din Septembrie 18, 2005, 15:14:30

Cu indentarea asta nu prea cred ca o sa aiba cineva chef sa iti citeasca sursa.

Titlul: usaco training ..sectiunea 1.4 .. checker challenge
Scris de: Cosmin Negruseri din Septembrie 18, 2005, 15:25:36

O chestie simpla ce ai putea sa o faci ar fi sa ai x = st[k] ca sa nu tot faci calculul adresei lui st[k] de atatea ori, probabil asta o sa te ajute putin, cat despre chestia cu implementarea iterativa sau recursiva nush daca te ajuta implementarea iterativa cu ceva, fa niste comparatii intre implementari pe calculatorul tau nu schimba o chestie doar pentru ca ai auzit ca merge mai bine altfel, convinge-te singur ce merge si ce nu. Alta chestie ar fi expresia

Cod:

diag[st[k]-k+n]!=val1 || diag2[k+st[k]]!=val1 || coloana[st[k]]!=val1

in care obligi programul sa evalueze toate trei expresiile iar schimband in

Cod:

!(diag[st[k]-k+n]==val1 && diag2[k+st[k]]==val1 && coloana[st[k]]==val1)

programul se opreste la prima expresie evaluata la false. Pentru rapiditate poti face acelasi algoritm de doua ori: o data cu scrierea primelor trei solutii si o data cu numararea solutiilor, ca sa nu faci if (gasite < 3) de atatea ori. Nu m-am uitat pe codu tau ca sa il inteleg ... astea sunt sugestii asa dintr-o privire fugara. (super tare handle .... )

infoarena

infoarena - concursuri, probleme, evaluator, articole => Informatica => Subiect creat de: tudor george cristian din Septembrie 14, 2005, 19:25:17