027 Loto

[•fluffy]

Aici puteţi discuta despre problema Loto.

[•ManolacheAdrian]

Am trimis 3 variante de solutii la problemea dupa cum urmeaza:
   1. Backtracking si primesc OK pe 5,6, TLE pe ultimele trei teste si WA in rest
    2. Solutia cu 6 for-uri si primesc WA pe 1..4 OK pe 5 si TLE in rest
    3. Solutia cu cautare binara si primesc OK pe 5,6 si WA in rest

Acuma cred ca nu mi-a m-ai ramas decat sa-mi iau lumea in cap si sa plec de acasa, asta daca nu binevoieste    cineva sa-mi dea vreun test
sa vad si eu unde gresesc.

[•rss1987]

Belea..daca nici solutia de N^6 n-o scrii corect?..nu cred ca o s-o faci prea curand. Trebuie sa te apuci serios de DEBUG... :lol:

uite aici o solutie N^6 corecta
compar-o cu a ta si vezi "diferenta"

Cod:

#include<stdio.h>
#define MAXN 101

FILE *in=fopen("loto.in","r"),*out=fopen("loto.out","w");
int N,S,V[MAXN];

void citesteDate()
{int i;
  fscanf(in,"%d %d",&N,&S);
  for(i=1;i<=N;i++)
     fscanf(in,"%d",&V[i]);
  fclose(in);
}

void proceseaza()
{int i,j,k,l,m,n;
  for(i=1;i<=N;i++)
      for(j=1;j<=N;j++)
         for(k=1;k<=N;k++)
             for(l=1;l<=N;l++)
                 for(m=1;m<=N;m++)
                     for(n=1;n<=N;n++)
                        if (V[i]+V[j]+V[k]+V[l]+V[m]+V[n]==S)
                           {fprintf(out,"%d %d %d %d %d %d\n",V[i],V[j],V[k],V[l],V[m],V[n]);
fclose(out);
return;}
 fprintf(out,"-1\n");
 fclose(out);
}

                   

 

int main()
{
 citesteDate();
 proceseaza();
 return 0;
}

Iei pe ea exact 35p daca o copiezi corect.  

Bafta la cautare N^3 * log(N^3)!

[edited by svalentin] foloseste [*code*][*/code*] (fara *) pentru a formata o sursa corect

[•greco]

Sau n^3.

[•ManolacheAdrian]

dupa ce nu dormi 48 de ore ajungi sa nu mai vezi bine...

[•cristy]

Eu am facut cu un back recursiv optimizat si am luat 70 de puncte dar totusi nu cred ca se rezolva cu back pentru ca sunt prea mari datele...dar daca faci cu un back destul de bun..faci peste 60 de pct...

[•ManolacheAdrian]

incearca back in heap poti sa iei 85+

[•skipy]

Din cate tin eu minte, am rezolvat problema f. usor: n^3 log (n^3), cu o cautare binara. Cred ca ar trebui sa fie usor acum...

[•cavendish]

Eu am facut N^3 * T, unde T ii timpu pt operatii cu mapurile din stl .

[•rss1987]

greco: si cati MB ai folosit pt. N^3. As presupune ca 37.5...nu ...la ONI trebuie sa te incadrezi in 15, deci e numai buna in N^3*log(N^3).

[•greco]

#define vmax 1000001

int n, m, s, lg, w[wmax], v[vmax][3], sol1, sol2, found;

--------------------

De fapt, daca ma gandesc mai bine (am facut de ceva timp problema) din 2 pasi de n^3 log n numai unul l-am redus la n^3.  
Imi cer scuze pentru inconvenientele cauzate.  

[•rss1987]

Se mai intampla...
  Se poate si in N^3 da cum ziceam mananca multa memorie...

[cristi8]

imi explica si mie cineva cum se face cautarea aia binara ?

..eu am facut problema cu 3 hash-table-uri... suma care se poate obtine cu 1,2 sau 3 numere..
..si dupa aia am facut n^3 pt primele 3 numere si am cautat restul sumei in ultimul hash..

[•druid]

Eu am facut un vector pt toate sumele posibile de 3 numere din fisierul de intrare... si apoi sortez vectorul asta si il parcurg de la inceput si pt fiecare suma fac cautare binare pt S-suma. Daca exista atunci reconstitui nr cu care s-a obtinut suma si S-suma. Trebuie ceva optimizari pt ultimele teste.

[•horax]

Eu am facut un vector pt toate sumele posibile de 3 numere din fisierul de intrare... si apoi sortez vectorul asta si il parcurg de la inceput si pt fiecare suma fac cautare binare pt S-suma. Daca exista atunci reconstitui nr cu care s-a obtinut suma si S-suma. Trebuie ceva optimizari pt ultimele teste.

Am facut exact ca si tine si pe ultimele 4 teste iau timp depasit.
Ce optimizari ai facut?
Eu am ordonat cu quick sort am facut cautare binara si totusi am timp depasit.
 

[u-92]

eu tot qsort+cautare binara am folosit si mi s-a incadrat f. bine in timp.. poate nu te opresti cand gasesti solutie.. nustiu de la ce altceva ar putea fi

[•horax]

eu tot qsort+cautare binara am folosit si mi s-a incadrat f. bine in timp.. poate nu te opresti cand gasesti solutie.. nustiu de la ce altceva ar putea fi

ma opresc, fac tot asa cum ai zis tu si totusi ...

[vladut.forum]

mah daca nimik altceva nu poate fii...atunci
nu faci bine cautarea binara
vezi cand intializezi left sa cresti cu unu
si cand initializezi right sa scazi cu unu
deci verifica sa fie
while (left<=right) {

tra la la
if (conditie1) {solutie; ma opresc;}
if (conditie2) left=(left+right)/2+1;
else right = (left+right)/2-1;
}
ceva imi spune ca sigur e asta
verifica si spunemi

[•Dorin]

la completarea vectorului cu sumele de trei numere, pana unde trebuie completat???
eu cred ca din cauza aia iau TLE la unele teste  :lol:

[VladS]

Pana la capat (N^3 numere). Nu de aici iei TLE.

[•Dorin]

Ok atunci e de la alteceva shi o sa mai optimizez poate intr-un final  iau shi eu 100 p.  

[•Dorin]

iau 95 de p WA testul unu  nu avetzi vreo idee de ce nu merge

pe alte rezolvari luam punctaj pe testul 1 ce ar pute sa aiba

[•bogdan2412]

Fa-ti un generator de teste si verifica ce da programul tau cu solutia N^6. O sa-ti foloseasca si la alte probleme de pe infoarena si in concursuri.

[•Dorin]

e o idee buna dar numerele cum le aleg ?? random sau crescator  ??
ca la suma nu e greu  

[•bogdan2412]

In general eu fac 100 teste random (stiu ca e cam exagerat, dar ... ) Fa-le cat de cat mici sa poti face debug dupa aia