1037 Produs

[•pauldb]

Aici puteti discuta despre problema Produs.

[•Bogdan_tmm]

daca faci operatii pe numere mari astfel:
st=dr=1;
a=1;//a nr mare
cat timp nu e sol
{
   daca a==numar
       break;
   daca a<numar
      a=a*(++dr);
   altfel
      a=a/(st++);
}

Dupa parerea mea solutia asta are complexitate O(10 000 * 100 000) aproximativ 1 miliard, dar ia 30p.
O optimizare ar fi sa transform numerele intr-o baza mai mare ca sa aibe mai putine cifre dar nu stiu cum. Any help?

[•DraStiK]

Poti obţine 80p daca logaritmezi numărul, dar nu stiu cum ai putea obţine 100p.

[•Bogdan_tmm]

Si cum anume logaritmezi un numar mare?
Marind baza nu ajuta?
L.E. am aflat

[•SpiderMan]

Se poate obtine 100p pe ideea lui Dragos, doar ca trebuie o baza mai mare, gen 10⁴.

[•airineiv]

Cum se poate logaritma un numar foarte mare?
Formula log_a(b*c) = log_ab + log_ac nu ajuta.

Any help?

[•Bogdan_tmm]

Sti ca numarul ala foarte mare e format astfel n*(n+1)*(n+2)*...*(n+m) unde 1<=n<=n+m<=100000 deci sti ca factorii primi sunt mai mici ca 100000 si astfel poti logaritma numarul ala mare

[•airineiv]

Multumesc pentru raspuns.

Am reusit sa logaritmez numarul ala mare dar nu obtin decat 80 de puncte, chiar daca logaritmez intr-o baza mai mare (100000 = 10e5).

Dau mai jos un fragment din codul meu:

Cod:

#define EPS 1e-6
#define LN10e5 11.512925464970228420089957273422

int Sgn(double logA, double logN)
{
	if(logA - logN < -EPS)
		return -1;
	else if(logA - logN > EPS)
		return 1;
	return 0;
}
unsigned int st=2, dr=1;
	double logA = 0.0;
	bool ok = false;
	while(!ok)
	{
		switch(Sgn(logA, logN))
		{
		case 0:
			ok = true;
			break;
		case -1:
			dr++;
			logA += log((double)dr) / LN10e5;
			break;
		case 1:
			logA -= log((double)st) / LN10e5;
			st++;
			break;
		default:
			break;
		}
	}

[•SpiderMan]

Incearca sa faci toate operatiile intr-o baza mai mare, poate asa merge .

[•airineiv]

Multumesc pentru raspuns, dar se pare ca nu ajuta asa mult marirea bazei. Am logaritmat chiar si in baza 10^50 (am folosit log10 ca logaritm in baza 10 si am impartit la 50, conform formulei de schimbare a bazei pentru logaritm).

Ultimele 2 teste pica testul de timp.

[•victor.ionescu]

Eu in concurs logaritmam numarul mare si apoi cautam binar pentru fiecare inceput.
Am luat 80. Dar nu baza logaritmului era problema la mine, ci baza in care tineam numarul mare.
Tu in ce baza tii numarul mare atunci cand il descompui in factori primi?

[•SpiderMan]

A reusit, cu baza 10⁴ e suficient ( si cred ca si la limita ) sa iei 100 pct.

[•victor.ionescu]

 bun 

[•airineiv]

Da, problema era la baza in care se tine numarul mare. Lua mult timp operatia de descompunere in factori primi a numarului mare, pentru ca foloseam baza 10.
Multumesc pentru ajutor.

[•R.A.R]

Imi poate spune cineva cum se logaritmeaza un numar mare ?Banuiesc ca se descompune in factori primi si va fi lg(nr) = p1*lg(f1)+p2*lg(f2)+..+pn*lg(fn)[fi = factorul i,pi = puterea la care apare factorul i in descompunere].Daca e asa,nu vor fi probleme cu 'precizia' ?

[•alexandru92]

lg(nr)=numaru de cifre-1 ( lg=logaritm in baza 10 )

[•R.A.R]

Am logaritmat numarul insa niciodata L == P chiar daca valorile sunt aceleasi.

Cod:

	while(L!=P)
	{
		if(L<P)
			L+=log10(++x);
		else
			L-=log10(++y);
	}

La valorile 5-8 ( cand ar trebui sa se opreasca), L = 2.52634 si P = 2.52634 insa imi cauta in continuare.

[•SpiderMan]

Vezi ca poate nu compara bine, adica din cauza zecimalelor. Incearca sa lucri cu double, daca nu ai facut-o pana acum. In rest, nu stiu ce sa zic.

[•R.A.R]

Problema e ca nu compara bine.Am folosit double,am inmultit cu puteri ale lui 10 pentru a elimina zecimalele dar lafel.

[•gcosmin]

Problema se poate rezolva si fara a folosi logaritmi, deci merge pe int fara erori de precizie. Solutia se foloseste de descompunerea in factori primi a numarului P si a numerelor posibile care pot aparea in produs (adica 1...100 000).

[•Bogdan_tmm]

Mai precis?
Impartirea lui P la fiecare factor prim (de putere_factor ori) iese din timp...

[•devilkind]

Nu chiar.
Gandeste ca ai de facut log2(N) + log3(N) + log5(N) + ... logP(N) impartirii (iar asta e un upper bound grosolan rau de tot) care in orice caz nu e foarte mare.

[•SpiderMan]

1. Trebuie sa citesti numarul in ordine inversa.
Ex: numarul 123456789123456789 va fi , dupa transformare, asa ( in vectorul v de la 1 -> 5 ) : 6789 2345 7891 3456 12 . Adica v[1] = 6789, v[2] = 2345 ....
2. Citeste subiectele propuse pana acum, sigur o sa te ajute.

[•SpiderMan]

Subiectele din acest topic.

[•adysnook]

Dupa ce am implementat si eu o solutie, 30p, si am citit comentariile, tot nu ma prind cum sa iau 100p.  Cum logaritmez P? e vorba de aproximari?