187 Ecuatii

[ditzone]

Aici puteţi discuta despre problema Ecuatii.

[•wefgef]

ce complexitate ati scos pe asta?

[andreit1]

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).

[•wefgef]

mie mi-a mers destul de bine un O(d^3) cu hash. nu stii unde as putea gasi solutia oficiala?

[andreit1]

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.

[•gogu]

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.

[•cristy]

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 ?...

[•cyron]

nu mai tin minte bine enuntzu dar parca trebuiau sa fie nenule

[•crawler]

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  ?

[•cos_min]

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

[•pauldb]

22822
1080000
6862
6096

Scuze...mai aveam un exemplu acolo

[•cos_min]

Eu am avut 4 teste, tu ai 5 raspunsuri 

[•c_sebi]

Spuneti-mi va rog ce imi scapa la algoritmul urmator 

Cod:

for (i=-50; i<=50; ++i)
  for (j=-50; j<=50; ++j)
    if (i*j)
      aduga -a1*i*i*i-a2*j*j*j in lista valorilor; 
for (i=-50; i<=50; ++i)
  for (j=-50; j<=50; ++j)
    for (k=-50; k<=50; ++k)
       if (i*j*k)
          daca a3*i*i*i+a4*j*j*j+a5*k*k*k se afla in lista valorilor
            nrsol=nrsol+1;

Multumesc!

[•MciprianM]

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.

[•b_ady20]

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...

[•belgun_adrian]

Spuneti-mi va rog ce imi scapa la algoritmul urmator 

Cod:

for (i=-50; i<=50; ++i)
  for (j=-50; j<=50; ++j)
    if (i*j)
      aduga -a1*i*i*i-a2*j*j*j in lista valorilor; 
for (i=-50; i<=50; ++i)
  for (j=-50; j<=50; ++j)
    for (k=-50; k<=50; ++k)
       if (i*j*k)
          daca a3*i*i*i+a4*j*j*j+a5*k*k*k se afla in lista valorilor
            nrsol=nrsol+1;

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.

[•cosmin79]

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

[•chibicitiberiu]

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, 
from /usr/include/c++/4.2/bits/ios_base.h:47,
 from /usr/include/c++/4.2/ios:48,
 from /usr/include/c++/4.2/istream:44, 
from /usr/include/c++/4.2/fstream:45, 
from user.cpp:3:

/usr/include/c++/4.2/bits/stl_function.h:134: error: expected identifier before numeric constant 
/usr/include/c++/4.2/bits/stl_function.h:134: error: expected unqualified-id before numeric constant
/usr/include/c++/4.2/bits/stl_function.h:143: error: expected identifier before numeric constant
/usr/include/c++/4.2/bits/stl_function.h:143: error: expected unqualified-id before numeric constant 

Aici e sursa...

Cod:

#define plus 1
#define minus 0
#include<fstream>
#include<cstdlib>
#include<cstring>
using namespace std;


int number[2], nx[2];

void check(char str[])
{
	int i = 0, len = strlen(str);
	int i2;
	char arr[5]; bool sign;
	int side = 0;
	int temp;

	while (i<len) {
		// check sign
		if (str[i] == '-') {
			sign = minus; i++;
		}
		else if (str[i] == '+') {
			sign = plus; i++;
		}

		// get number
		i2 = 0;
		while (str[i] >= '0' && str[i] <= '9') {
			arr[i2] = str[i];
			i2++; i++;
		}
		temp = atoi(arr);
		if (sign == minus) temp*=-1;
		memset(arr, 0, 5);

		// check if x and make calculations
		if (str[i] == 'x') {
			nx[side]+=temp;
			i++;
		}
		else number[side]+=temp;

		if (str[i] == '=') {
			i++; side++;
		}
	}
}



int main()
{
	int n; long long result;
	char str[256];

	ifstream in ("ecuatii.in");
	ofstream out ("ecuatii.out");
	in>>n;

	in.getline(str, 256, '\n');

	for (int i = 0; i < n; i++) {
		memset(str, 0, 256);
		number[0] = 0; number[1] = 0;
		nx[0] = 0; nx[1] = 0;
		in.getline(str, 256, '\n');
		check(str);

		if ((nx[0] == nx[1]) && (number[0] == number[1]))
			out<<"infinit\n";

		else if ((nx[0] == nx[1]) && (number[0] != number[1]))
			out<<"imposibil\n";

		else {
			number[0] = number[0] - number[1];
			nx[0] = nx[0] - nx[1];
			result = (long long)(10000*number[0])/nx[0]*-1;

			out<<result/10000<<"."<<abs(result%10000)<<endl;
		}
	}
	out.close();
	in.close();
	return 0;


}

Are cineva vreo idee de ce apare eroarea? E ciudat ptr ca in Visual Studio a mers...

[•klamathix]

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 ).

[•chibicitiberiu]

Da ai dreptate...      era ecuatii2, nu m-am mai uitat la cerinta  ms mult

[•nash]

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. "

[•dutzul]

imi poate zice cineva raspunsul pt 5 6 -1 5 0
iau wa pe testele 2-3 ]

[•dutzul]

am gasit greseala imi baga prea multe elemente cand era doar un 0

[•VisuianMihai]

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 . Nu numaram toate solutiile in unele cazuri...

[•Fayed]

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;
}