148 Numere 2

[•domino]

Aici puteţi discuta despre problema Numere 2.

[•Prostu]

nu stiu, dar orice fac nu reusesc sa iau peste 75 de puncte la problema asta... am implementat numerele mari in baza 1000000000 si in rest pentru fiecare putere (340-1) fac o cautare binara pentru baza, dar pe testele 1,3,4,6,7 iau TLE...

P.S. numerele mari le-am implementat sub forma de clasa

[•Prostu]

   
Puterile sunt intre 1 si 335... luam maxim 90 pct cu for-ul intre 2 si 335...
(2^335 are aprox 100 cifre)
Am redus la 200, luam ba testul 1 ba testul 6 TLE, ba amandoua...
Am redus la 150 si hop... 100 pct...

[•fireatmyself]

             
asta e chiar trist ... mai ales pentru cei care au implementat solutia corecta in timpul concursului ...

malex ar trebui ars pe rug   ma duc sa strang paie. care vine cu mine ?

[•pauldb]

Stiu ca e cam tarziu postul meu, dar ce am vazut in acest topic m-a pus pe ganduri. 

Eu am luat 100 cu o sursa in Pascal care for-ul de la 335 si timpul maxim pe test a fost 0.12s. 

[•Prostu]

Eu am implementat numerele mari sub forma de clasa, pentru ca este mai usor de lucrat cu ele sub aceasta forma.

O implementare a numerelor mari sub forma de clasa merge in medie de 3-4 ori mai incet decat o implementare cu functii separate pt operatii.
Diferenta se datoreaza modului de implementare destul de comod pe care l-am adoptat. Astfel sunt necesare destul de multe duplicari si copierii elementelor operatiilor (atat rezultatul, cat si cel de-al doilea operator, singurul transmis prin pointer este primul operator) ceea ce consuma destul de mult timp.
Nu am optimizat pana acum forma in care implementez numere mari, pentru ca, pana acum au fost doar 2 probleme la care sa iau TLE (aceasta si Gard 3).
O sa ma gandesc la o implementare mai eficienta a numerelor mari sub forma de clasa. (prima idee ar fi sa nu mai folosesc vectori statici si sa folosesc in schimb clasa vector din std)
Daca stie cineva o implementare eficienta a numerelor mari sub forma de clasa, PM sau sa posteze in topic-ul Informatica.

[nash_mit]

 Da' de ce neaparat folosind OPP ? Daca te uiti la implemtetarea de la "multe smenuri .." o sa iti faci o idee destul de buna ..+ nu e deloc greoi ... ceva bun este psihologia concursurilor de informatica de catalin francu ..... inveti destule din implementarile amintite ...

[•Prostu]

Pentru ca este mult mai usor de lucrat cu numerele mari astfel. Nu pentru ca sunt greu de folosit si implementat sub forma de functii individuale.
Daca ai o formula mai complicata scrii direct

Cod:

Mare a, b, c, d;
...
Mare rez;
rez = ((a + b) * (c - d)) / 5;
//si eventual
return rez;

Apropo, de la ce vine abrevierea OPP . Eu stiam ca in engleza i se spune OOP (Object Oriented Programming) si in romana POO (Programare Orientata pe Obiecte)

[nivan]

dap...  OOP = Object Oriented Programming

[•greco]

E mult mai elegant sa faci numerele mari cu clase, si ai mult mai putine griji odata ce ai scris codul pt. ele. Din pacate insa la multe concursuri din Romania (ONI, lot), limitele de timp sunt foarte stranse si nu iti permiti sa faci asa. Mai ales din Romania pt. ca oricum doar in Romania se dau probleme la care trebuie sa folosesti numere mari.

[•marius135]

vreau si eu un test cel mai mic daca se poate....
ca la mine pe comp merg teste dar pe evaloator imi da incorect instantaneu lucru ciudat ca mie imi ruleaza cateva secunde....
deci un test(din alea oficiale daca se poate) multumesc anticipat

[•Florian]

Din ce stiu nu se publica teste oficiale...

[•bogdan2412]

Testele de la această problemă conţineau caractere invalide la sfârşitul testelor. Problema a fost reevaluată, însă nu ar trebui să se schimbe niciun scor.

[•Michel]

pe teste mici imi da rsp gresit, la cele mari imi iese din timp, dar la cateva imi da bn, si iau doar 25 de pct, si nu stiu dc, dak aveti vreo idee... uite sursa

Cod:

#include<math.h>
#include<fstream>
using namespace std;
int p,a,b,d;
int pr;
int main ()
{
	ifstream f("numere2.in.txt");
	f>>p;
	a=1;
	b=p-1;
	ofstream g("numere2.out.txt");
	if(p==0)
	{
		g<<'0';
		return 0;
	}
	if(p==1)
	{
		g<<'1'<<'\n'<<'1';
		return 0;
	}
	else
	{
		pr=1;
		if(p%2==0)
			pr=0;
		for(d=3;(d*d)<=p&&pr;d=d+2)
			if(p%d==0)
				pr=0;
    }
	if(pr)
	{
		g<<p<<'\n'<<'1';
		return 0;
    }
	if(!pr)
		do
		{
			a++;
			while(double (pow( double (a), double (b)))>p)
				b--;
			if(double(pow(double(a),double(b)))==p)
			{	
				g<<a<<'\n'<<b<<'\n';
				return 0;
			}
		}while( double (pow( double (a), double (b)))<=p);
		
	return 0;
	
}

Editat de admin: Foloseste tagul code.

[•sYnceD]

I-au doar 50 ... primele 10 teste imi da incorect ... restu 10 OK!