infoarena

infoarena - concursuri, probleme, evaluator, articole => Arhiva de probleme => Subiect creat de: Paul-Dan Baltescu din Mai 10, 2010, 07:57:50


Titlul: 1037 Produs
Scris de: Paul-Dan Baltescu din Mai 10, 2010, 07:57:50
Aici puteti discuta despre problema Produs (http://infoarena.ro/problema/produs).

Titlul: Răspuns: 1037 Produs
Scris de: Tirca Bogdan din Mai 13, 2010, 13:18:29
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?

Titlul: Răspuns: 1037 Produs
Scris de: Dragos Oprica din Mai 13, 2010, 14:28:58
Poti obţine 80p daca logaritmezi numărul, dar nu stiu cum ai putea obţine 100p. :)

Titlul: Răspuns: 1037 Produs
Scris de: Tirca Bogdan din Mai 13, 2010, 22:02:00
Si cum anume logaritmezi un numar mare?
Marind baza nu ajuta?
L.E. am aflat :D

Titlul: Răspuns: 1037 Produs
Scris de: Simoiu Robert din Mai 16, 2010, 12:35:21
Se poate obtine 100p pe ideea lui Dragos, doar ca trebuie o baza mai mare, gen 104.

Titlul: Răspuns: 1037 Produs
Scris de: Airinei Vasile din Mai 24, 2010, 15:20:59
Cum se poate logaritma un numar foarte mare?
Formula loga(b*c) = logab + logac nu ajuta.

Any help?

Titlul: Răspuns: 1037 Produs
Scris de: Tirca Bogdan din Mai 25, 2010, 12:13:43
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

Titlul: Răspuns: 1037 Produs
Scris de: Airinei Vasile din Mai 25, 2010, 22:35:44
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;
		}
	}

Titlul: Răspuns: 1037 Produs
Scris de: Simoiu Robert din Mai 26, 2010, 09:04:10
Incearca sa faci toate operatiile intr-o baza mai mare, poate asa merge .

Titlul: Răspuns: 1037 Produs
Scris de: Airinei Vasile din Mai 26, 2010, 09:37:20
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.

Titlul: Răspuns: 1037 Produs
Scris de: Ionescu Victor Cristian din Mai 26, 2010, 18:11:50
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?

Titlul: Răspuns: 1037 Produs
Scris de: Simoiu Robert din Mai 26, 2010, 19:54:27
A reusit, cu baza 104 e suficient ( si cred ca si la limita ) sa iei 100 pct.

Titlul: Răspuns: 1037 Produs
Scris de: Ionescu Victor Cristian din Mai 26, 2010, 21:08:41
 bun  :ok:

Titlul: Răspuns: 1037 Produs
Scris de: Airinei Vasile din Mai 26, 2010, 21:45:44
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. \:D/ :yahoo:

Titlul: Răspuns: 1037 Produs
Scris de: FMI Romila Remus Arthur din Mai 27, 2010, 20:45:15
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' ?

Titlul: Răspuns: 1037 Produs
Scris de: alexandru din Mai 28, 2010, 11:04:09
lg(nr)=numaru de cifre-1 ( lg=logaritm in baza 10 )

Titlul: Răspuns: 1037 Produs
Scris de: FMI Romila Remus Arthur din Mai 30, 2010, 10:39:04
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.

Titlul: Răspuns: 1037 Produs
Scris de: Simoiu Robert din Mai 30, 2010, 11:20:02
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.

Titlul: Răspuns: 1037 Produs
Scris de: FMI Romila Remus Arthur din Mai 30, 2010, 11:42:12
Problema e ca nu compara bine.Am folosit double,am inmultit cu puteri ale lui 10 pentru a elimina zecimalele dar lafel.

Titlul: Răspuns: 1037 Produs
Scris de: Gheorghe Cosmin din Mai 30, 2010, 11:45:34
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).

Titlul: Răspuns: 1037 Produs
Scris de: Tirca Bogdan din Mai 30, 2010, 11:59:59
Mai precis?
Impartirea lui P la fiecare factor prim (de putere_factor ori) iese din timp...

Titlul: Răspuns: 1037 Produs
Scris de: Savin Tiberiu din Mai 30, 2010, 12:22:07
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.

Titlul: Răspuns: 1037 Produs
Scris de: Simoiu Robert din Iunie 08, 2010, 14:22:44
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.

Titlul: Răspuns: 1037 Produs
Scris de: Simoiu Robert din Iunie 09, 2010, 07:13:06
Subiectele din acest topic.

Titlul: Răspuns: 1037 Produs
Scris de: Adrian Munteanu din Mai 29, 2012, 12:08:39
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?

Titlul: Răspuns: 1037 Produs
Scris de: nagisa din Martie 26, 2016, 21:56:16
La problema asta nu este cam stransa limita de timp??? :readthis:


Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines