Imprimă pagina - 148 Numere 2

Titlul: 148 Numere 2
Scris de: Mircea Pasoi din Decembrie 12, 2005, 00:17:36

Aici puteţi discuta despre problema Numere 2 (http://infoarena.ro/problema/numere2).

Titlul: 148 Numere 2
Scris de: Stefan-Alexandru Filip din Decembrie 13, 2005, 00:04:06

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

Titlul: 148 Numere 2
Scris de: Stefan-Alexandru Filip din Decembrie 16, 2005, 21:18:18

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

Titlul: 148 Numere 2
Scris de: Bogdan-Alexandru Stoica din Decembrie 16, 2005, 23:09:54

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

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

Titlul: Raspuns: 148 Numere 2
Scris de: Paul-Dan Baltescu din August 14, 2006, 11:09:31

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

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

Titlul: Re: 148 Numere 2
Scris de: Stefan-Alexandru Filip din August 14, 2006, 20:45:12

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.

Titlul: Raspuns: 148 Numere 2
Scris de: nash_mit din August 17, 2006, 23:18:03

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

Titlul: Re: 148 Numere 2
Scris de: Stefan-Alexandru Filip din August 18, 2006, 12:21:45

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)

Titlul: Raspuns: Re: 148 Numere 2
Scris de: nivan din August 18, 2006, 19:37:46

dap... OOP = Object Oriented Programming

Titlul: Re: 148 Numere 2
Scris de: Tiberiu-Lucian Florea din August 19, 2006, 03:10:23

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

Titlul: Răspuns: 148 Numere 2
Scris de: Dumitran Adrian Marius din Aprilie 07, 2007, 20:18:48

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

Titlul: Răspuns: 148 Numere 2
Scris de: Florian Marcu din Aprilie 07, 2007, 20:20:57

Din ce stiu nu se publica teste oficiale... :?

Titlul: Răspuns: 148 Numere 2
Scris de: Bogdan-Cristian Tataroiu din Martie 21, 2010, 17:49:25

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.

Titlul: Răspuns: 148 Numere 2
Scris de: Jumatate Teodor-Mihail din Aprilie 09, 2012, 17:23:56

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.

Titlul: Răspuns: 148 Numere 2
Scris de: Alin Cosmin din Iunie 12, 2014, 18:31:59

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

infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Mircea Pasoi din Decembrie 12, 2005, 00:17:36