Titlul: 187 Ecuatii Scris de: ditzone din Martie 03, 2006, 18:23:10 Aici puteţi discuta despre problema Ecuatii (http://infoarena.ro/problema/eqs).
Titlul: 187 Ecuatii Scris de: Andrei Grigorean din Martie 03, 2006, 21:59:16 ce complexitate ati scos pe asta?
Titlul: 187 Ecuatii Scris de: andreit1 din Martie 03, 2006, 22:31:26 O(D^3) unde D este lungimea intervalului unde se cauta solutiile( aici 100), dar cu o gramada de memorie folosita. Solutia de la ONI era O(D^3*logD).
Titlul: 187 Ecuatii Scris de: Andrei Grigorean din Martie 03, 2006, 22:44:11 mie mi-a mers destul de bine un O(d^3) cu hash. nu stii unde as putea gasi solutia oficiala?
Titlul: 187 Ecuatii Scris de: andreit1 din Martie 03, 2006, 23:47:33 http://info.devnet.ro/download.php?page=cat&cat=23
Eu de aici mi-am luat ONI-urile. Vad ca acum au aparut si loturile acolo. Titlul: 187 Ecuatii Scris de: Gogu Marian din Martie 03, 2006, 23:57:50 Eu am facut initial O(D^3*logD) dar am redus pana la O(D^3) cu O(D^2) memorie folosita (fara hash).
Ar fi mers si cu compilatoare de 16 biti. Trebuiau sa bage limitele un pic mai mari la ONI cred. Titlul: Raspuns: 187 Ecuatii Scris de: Rus Cristian din Aprilie 11, 2006, 11:31:57 am o nelamurire la problema asta...nu exita cel putin o solutie...pt fiecare ecuatie?...am gasit testele de la problema asta....sau...unele din ele...si...am vazut ca pt 41 43 47 0 0 solutia e 0....de ce nu se ia in considerare si solutia 0-0-0-0-0 ?...
Titlul: Raspuns: 187 Ecuatii Scris de: sorin fagateanu din Aprilie 11, 2006, 11:41:14 nu mai tin minte bine enuntzu dar parca trebuiau sa fie nenule
Titlul: Răspuns: 187 Ecuatii Scris de: Puni Andrei Paul din Mai 20, 2007, 19:46:49 Citat a1*x1 + a2*x2 + a3*x3 + a4*x4 + a5*x5 + a6*x6=0 cam asta apare in enunt ... nu ar trebui sa fie pana la x5 :thumbup: ? Titlul: Răspuns: 187 Ecuatii Scris de: Bondane Cosmin din Mai 21, 2007, 20:20:06 O mica rugaminte am, sa va uitati cat va pentru urmatoarele teste :
-2 -9 3 2 6 5 6 -1 0 0 24 32 8 -6 -7 50 -50 50 -50 1 Titlul: Răspuns: 187 Ecuatii Scris de: Paul-Dan Baltescu din Mai 21, 2007, 20:33:53 22822
1080000 6862 6096 Scuze...mai aveam un exemplu acolo :) Titlul: Răspuns: 187 Ecuatii Scris de: Bondane Cosmin din Mai 21, 2007, 21:33:30 Eu am avut 4 teste, tu ai 5 raspunsuri ???
Titlul: Răspuns: 187 Ecuatii Scris de: Sebastian Crisan din Iunie 27, 2007, 19:34:05 Spuneti-mi va rog ce imi scapa la algoritmul urmator :-'
Cod: for (i=-50; i<=50; ++i) Multumesc! Titlul: Răspuns: 187 Ecuatii Scris de: MciprianM din Noiembrie 21, 2008, 19:47:34 Pentru datele de intrare:
0 0 0 0 0 raspunsul e 10 000 000 000, care nu incape pe tipul de date int, iar solutia mea care ia 100p memoreaza raspunsul intr-o variabila de tipul int. Cred ca mai trebuie un test. Titlul: Răspuns: 187 Ecuatii Scris de: Branescu Adrian din Martie 29, 2009, 21:54:25 voi ce metoda ati folosit? ca eu memorez -a1*x1^3-a2*x2^3 intr-un vector de 10000 lungime, apoi sortez vectorul cu quicksort, generez celelalte 3 necunoscute si pentru fiecare a3*x3^+a4*x4^3+a5*x5^3 caut in vector folosind cautarea binara, daca gasesc incrementez numarul solutilor... dar nu inteleg, pe free pascal imi dau tot felul de erori cand rulez programul si pe evaluator imi tot da TLE, iar dupa cateva modificari ale tipurilor variabilelor mai iau cate 10 puncte, apoi iarasi WA peste tot... nu mai inteleg nimic ](*,) M-am uitat in solutia oficiala si exact aceeasi metoda o recomanda si ei :)... help, please...
Titlul: Răspuns: 187 Ecuatii Scris de: Belgun Dimitri Adrian din Aprilie 07, 2009, 07:57:04 Spuneti-mi va rog ce imi scapa la algoritmul urmator :-' Cod: for (i=-50; i<=50; ++i) Multumesc! In cazul in care -a1*i*i*i-a2*j*j*j a mai fost deja calculat ce faci? Incearca sa analizezi cazul asta. Si eu ma blocasem la 20, dar cu o mica modificare ajunsai la 100. Titlul: Răspuns: 187 Ecuatii Scris de: Carabet Cosmin Andrei din Iunie 05, 2009, 21:58:12 sunt putin nedumerit la problema asta.iau tle pe toate testele....Am facut asa:
1.calculez cu 2 foruri valorile pt a4*x4^3+a5*x5^3 si le retin intr-un vector.Sortez vectorul cu sort din stl 2.Fac 3 foruri si vad sumele S=a1*x1^3+a2*x2^3+a3*x3^3.Pe urma caut binar in vectorul calculat anterior pt fiecare suma S , -S. 3.dupa ce gasesc pozitia cea mai mare pt care v[poz]=-S, merg inapoi si vad pana la ce pozitie v[poz]=-S,iar apoi actualizez rezultatul final Sper ca am fost destul de clar. Ma lamureste si pe mine cineva unde-i problema va rog? ??? later edit: asa se intampla daca nu scrii corect numele fisierelor de intrare si de iesire :)) .scz pt post Titlul: Răspuns: 187 Ecuatii Scris de: Chibici Tiberiu din Martie 03, 2010, 22:49:19 Mi-a iesit problema, in Visual Studio 2008 merge perfect, dar aici obtin eroare de compilare...
Cod: Eroare de compilare: In file included from /usr/include/c++/4.2/string:53, from /usr/include/c++/4.2/bits/locale_classes.h:47, Aici e sursa... Cod: #define plus 1 Are cineva vreo idee de ce apare eroarea? E ciudat ptr ca in Visual Studio a mers... Titlul: Răspuns: 187 Ecuatii Scris de: Mihai Calancea din Martie 03, 2010, 23:40:41 De la 'plus' si 'minus' ti se trage , exista niste chestii prin stl care se numesc la fel si intra in conflict. Btw , ai gresit problema , cred ca tu cauti ecuatii2 ( aia de la oji clasa a X-a ).
Titlul: Răspuns: 187 Ecuatii Scris de: Chibici Tiberiu din Martie 04, 2010, 08:06:41 Da ai dreptate... :oops: :rotfl: era ecuatii2, nu m-am mai uitat la cerinta :) ms mult
Titlul: Răspuns: 187 Ecuatii Scris de: nash mit din Aprilie 15, 2010, 16:05:09 Problema asta nu ar trebui sa aiba cel putin doua teste cu X4 = X5 = 0 ?? si cel putin 4 teste X5 = 0 ?? " un program care functioneaza perfect pentru a4=a5=0 va obtine cel putin 20 de puncte. Un program care functioneaza perfect pentru a5=0 va obtine cel putin 40 de puncte. "
Titlul: Răspuns: 187 Ecuatii Scris de: Bodnariuc Dan Alexandru din Decembrie 31, 2011, 15:28:05 imi poate zice cineva raspunsul pt 5 6 -1 5 0
iau wa pe testele 2-3 ] :x Titlul: Răspuns: 187 Ecuatii Scris de: Bodnariuc Dan Alexandru din Decembrie 31, 2011, 16:03:50 am gasit greseala imi baga prea multe elemente cand era doar un 0 :thumbup:
Titlul: Răspuns: 187 Ecuatii Scris de: Mihai Visuian din Iunie 09, 2012, 11:12:12 la testul din exemplu imi da 652 in loc de 654 si nu inteleg de ce.
Am inserat intai toate valorile -a1*x1^3-a2*x2^3, dupa care am verificat daca gasesc a3*x3^3+a4*x4^3+a5*x5^3. Later Edit: Am rezolvat :D. Nu numaram toate solutiile in unele cazuri... Titlul: Răspuns: 187 Ecuatii Scris de: Stratulat Alexandru din Martie 06, 2013, 15:34:28 Am incercat si eu sa fac problema si nu inteleg unde gresesc. Am wa dar totusi soloutie mea este aproape de alte exemple, insa nu stiu
ce nu fac bine. Salvez toate solutiile posibile a primelor 2 necusoncute apoi caut toate solutiile posibile pentru urmatoarele 3 necunoscute astfel incat suma lor sa fie egala cu opusul sumei primelor 2. Iata si codul meu : #include <cstdio> #include <vector> #include <stdlib.h> #define NMAX 660000 using namespace std; int V[5]; vector < int > Hash[NMAX]; int Nmax; void citesc(){ freopen("eqs.in","r",stdin); freopen("eqs.out","w",stdout); for(register int i=1;i<=5;++i) scanf("%d",&V); } int search(int X){ int key = abs(X%NMAX); for(vector < int >::iterator it = Hash[key].begin();it!=Hash[key].end();++it) if(*it == X) return 1; return 0; } void add(int X){ int key = abs(X%NMAX); Hash[key].push_back(X); } void solve(){ for(int i=-50;i<=50;++i) for(int j=-50;j<=50;++j) add(-V[1]*i*i*i - V[2]*j*j*j); for(int k=-50;k<=50;++k) for(int i=-50;i<=50;++i) for(int j=-50;j<=50;++j) if(search(V[3]*k*k*k + V[4]*i*i*i + V[5]*j*j*j)) Nmax++; } int main(){ citesc(); solve(); printf("%d",Nmax); return 0; } Titlul: Răspuns: 187 Ecuatii Scris de: Pirtoaca George Sebastian din Martie 06, 2013, 17:24:48 Cod: int search(int X){ Titlul: Răspuns: 187 Ecuatii Scris de: Stratulat Alexandru din Martie 06, 2013, 20:39:59 Ok, am modificat in sensul ca de fiecare cand gasesc un rezultat al sume i^3 + j^3 + K^3 scot din hash valoarea respectiva si tot nu imi da bine. De ex pe codul meu imi da 109 de 654. Sorry dar tot nu reusesc sa imi dau seama ce nu e bine ](*,).
Iata ce am modificat fata de data trecuta: Am facut o functie remove void remove(int X){ int key = abs(X%NMAX); for(vector < int >::iterator it = Hash[key].begin();it!=Hash[key].end();++it) if(*it == X){ Hash[key].erase(it); return ; } } si cand numar solutiile fac asta : for(int k=-50;k<=50;++k) for(int i=-50;i<=50;++i) for(int j=-50;j<=50;++j) if(search(V[3]*k*k*k + V[4]*i*i*i + V[5]*j*j*j)){ Nmax++; remove(V[3]*k*k*k + V[4]*i*i*i + V[5]*j*j*j); } Titlul: Răspuns: 187 Ecuatii Scris de: Pirtoaca George Sebastian din Martie 06, 2013, 21:00:40 Nu trebuie sa le scoti din hash. Faci asa:
Cod: int search(int X){ Titlul: Răspuns: 187 Ecuatii Scris de: Stratulat Alexandru din Martie 07, 2013, 22:31:43 Da .. mi-am dat seama ce nu facusem bine. Acum am luat 100. Mersi mult :D :peacefingers:
Titlul: Răspuns: 187 Ecuatii Scris de: one shot din Iulie 15, 2016, 23:21:34 ce e gresit?
#include <cstdio> #include <algorithm> using namespace std; int v[1000005],v2[1000005],n,m,i,a,b,c,d,e,k1,k2,k3,st,dr,pos,mij; long long sol; int main() { freopen("eqs.in","r",stdin); freopen("eqs.out","w",stdout); scanf("%d%d%d%d%d",&a,&b,&c,&d,&e); for(k1=-50;k1<=50;k1++) for(k2=-50;k2<=50;k2++) for(k3=-50;k3<=50;k3++) v[++m]=a*k1*k1*k1+b*k2*k2*k2+c*k3*k3*k3; for(k1=-50;k1<=50;k1++) for(k2=-50;k2<=50;k2++) v2[++n]=d*k1*k1*k1+e*k2*k2*k2; sort(v2+1,v2+n+1); for(i=1;i<=m;i++) { st=1; dr=n; pos=0; while(st<=dr) { mij=(st+dr)/2; if(v2[mij]<=-v) { pos=mij; st=mij+1; } else dr=mij-1; } while(v2[pos]==-v&&pos>0) { sol++; pos--; } } printf("%lld",sol); return 0; } Titlul: Răspuns: 187 Ecuatii Scris de: Bogdan Pop din Iulie 16, 2016, 13:50:35 ce e gresit? Vezi ca solutiile trebuie sa fie nenule.Solutia te merge(cel putin pe exemplu,pe care am verificat-o) daca pui conditia k1!=0&&k2!=0&&k3!=0 peste tot unde apar variabilele.#include <cstdio> #include <algorithm> using namespace std; int v[1000005],v2[1000005],n,m,i,a,b,c,d,e,k1,k2,k3,st,dr,pos,mij; long long sol; int main() { freopen("eqs.in","r",stdin); freopen("eqs.out","w",stdout); scanf("%d%d%d%d%d",&a,&b,&c,&d,&e); for(k1=-50;k1<=50;k1++) for(k2=-50;k2<=50;k2++) for(k3=-50;k3<=50;k3++) v[++m]=a*k1*k1*k1+b*k2*k2*k2+c*k3*k3*k3; for(k1=-50;k1<=50;k1++) for(k2=-50;k2<=50;k2++) v2[++n]=d*k1*k1*k1+e*k2*k2*k2; sort(v2+1,v2+n+1); for(i=1;i<=m;i++) { st=1; dr=n; pos=0; while(st<=dr) { mij=(st+dr)/2; if(v2[mij]<=-v) { pos=mij; st=mij+1; } else dr=mij-1; } while(v2[pos]==-v&&pos>0) { sol++; pos--; } } printf("%lld",sol); return 0; } Titlul: Răspuns: 187 Ecuatii Scris de: Andrei C. Diaconu din Septembrie 23, 2016, 18:55:27 Salut! Nu ar fi mai bine sa precizati ca solutiile trebuie sa fie nenule? Am stat cam o ora sa ma prind ca asta era gresit.... :angry: . Daca cineva care citeste acest mesaj are privilegiul de a modifica textul il rog sa-l corecteze!
|