003 Fractii

[nivan]

Pentru testele cu numere mici, nu stiu... dar tie ti-ar trebui un vector de 607927104783 nu de 1000000. Incearca sa rezolvi problema fara a generea sau a numara fractiile. Nu cred ca o sa-ti mearga pe principiul asta.......  Ideea e ca, chiar daca ai putea sa aloci un vector de 607927104783, nu ti s-ar mai incadra in timpul de executie programul (din cauza numarului mare de operatii). 

[•k_ounu_eddy]

Deci tu imi sugerezi practic sa ma gandesc la un nou algoritm?Cred ca daca mi-ar merge sa aloc memorie unui vector de 607927104783,mi s-ar incadra in timp.Cel putin asa cred.

[nivan]

 Poi intrucat tu completezi un vector de 607927104783, inseamna ca faci cel putin 607927104783 operatii (cred... sper ca nu zic vreo tampenie) si nush daca 607927104783 oferatii intra in timp... imi pare un numar destul de mare.  Da poate reusesti sa completezi mai repede(desi nu prea vad cum).... explica cum completezi tu fractiile.
 Daca metoda ta e ca din fiecare fractie x/y derivi alte 2 fractii.... nu cred ca va intra in timp.

[Last Edit] Daca chiar vrei sa mergi pe varianta asta, poti sa retii doar penultimul si ultimul rand din triunghiul ala de l-ai reprezentat pe pagina 4. Astfel cred ca iti va ajunge memoria.

[•k_ounu_eddy]

Da asa fac dintr-o fractie deriva doua.Deci eu pornesc de la fractia 1/1.(la primul apel i=1 si j=1).Apoi pun un while si dau conditia ca atata timp cat in vectorii numitor si numarator mai exista o fractie a caror suma sa fie mai mica ca n,din fractia gasita,sa derive alte doua.Sper ca m-am facut inteles destul de bine.Daca nu,am voie sa postez codul?

[nivan]

Am inteles, cat despre cod... mai demult era voie, acum nu mai stiu. Oricum nu cred ca se supara nimeni ca-l posetezi, doar sa nu postezi solutii de 100 puncte.
Eu unu chiar as fi curios legat de codul tau, in primul rand ce complexitate are, desi mie imi pare destul de maricica, din cate ai postat pan' acu. 

[•k_ounu_eddy]

asta e codul :

Cod:

#include <stdio.h>
int main()
{
unsigned long *numitor,*numarator;
numitor=new unsigned long[1000000];
numarator=new unsigned long[1000000];
int k,n;
numarator[1]=1;numitor[1]=1;k=1;
scanf("%d",&n);
int gata=0;
	while(!gata)
	{gata=1;
	for(int i=k;i<=k;i++)
		if(numarator[i]+numitor[i]<=n)
		{k++;
		 numitor[k]=numarator[i]+numitor[i];
		 numarator[k]=numarator[i];
		 k++;
		 numarator[k]=numitor[i]+numarator[i];
                 numitor[k]=numitor[i];
                 gata=0;
		}
	}
printf("%ld\n",k);
return 0;
}

[•Adriana_S]

Tu stii ca nu folosesti fisiere nu? Adica nu ai trimis codu' chiar asa, right?

[•wefgef]

Deci tu imi sugerezi practic sa ma gandesc la un nou algoritm?Cred ca daca mi-ar merge sa aloc memorie unui vector de 607927104783,mi s-ar incadra in timp.Cel putin asa cred.

ti-ar intra in timp.. daca ar fi timpul de executie cateva luni .

ca sa rezolvi corect aceasta problema cel mai bine e sa urmezi sfaturile pe care ti le-a dat azotlichid in topicul pe care l-ai creat tu. 

[•k_ounu_eddy]

Bineinteles ca nu am trimis asa.
Deci trebuie sa ma gandesc din nou cum sa optimizez algoritmul care l-ati implementat voi.
Am o intrebare ,Ciurul lui Erastotene calculeaza numerele prime mai mici ca n ,dar mie imi trebuiesc numerele prime cu n.De asemenea alta intrebare ar fi daca trebuie sa folosesc ambele functii si totient si ciurul.

[•svalentin]

Ai citit toate posturile de pe topicul asta? .. sunt multe indicii prin ele

[•alex_damian]

Nu stiu daca e locul bun unde sa postez, dar pot sa primesc un test oarecare cu raspunsul la aceasta problema?

Pe testele astea imi da corect, totusi iau 0 puncte..

N -> Rezultat

11 -> 83
15 -> 143
31 -> 615
99 -> 6007
100 -> 6087
1000000 -> 607927104783

Sper sa fi copiat bine Smile
Succes!

Silviu

e vreo problema cu evaluarea la problema asta ??

[•pauldb]

Nu este nici o problema cu evaluarea la problema asta. Am luat 100 acuma.
Si te sfatuiesc sa folosesti citate cand copiezi mesajele altor utilizatori.

[•alex_damian]

hmz ... ciudat pentru ca acu vreo 2 luni am trimis sursa unui prieten care lua 100 pcte la el si eu tot 0 luam

poti sa verifici niste teste randomed?

123456 - 9265674079
847325 - 436467869023
648812 - 255911628103
999999 - 607926304783
71354 - 3095252991

ms anticipat.

ps: nu e nevoie de operatii pe numere mari, nu ?
ps2: era cu copy paste sry...

[•pauldb]

Sunt bune rezultatele tale. Nu inteleg de ce iei 0. 
Cat despre numere mari, e clar ca solutia este <= N^2 (deci nu e nevoie de numere mari).

[•alex_damian]

mda, ciudat

[•jdv]

Mie nu mi se uploadeaza sursa...
E cam mare ce-i drept(534kb)...dar ar trebui sa functioneze...nu?

[•devilkind]

da ce ai scris ma acolo ?? romane, jurnalu tau intim ), just kiddin

oricum eu te sfatuiesc sa incerci sa mai reduci dimensiunea sursei si sa incerci din nou.

[•cos_min]

@Jecan Daniel Valerian

Tu ai precalculat tot ? 

[•jdv]

Nu am precalculat...doar ca am declarat un vector cu 78498 de constante...cred ca stii cu ce...
Si tocmai de aceea e asa mare...

As putea incerca si cu jurnalul dar nu cred ca o sa-mi compileze...

[•jdv]

Are rost sa incerc sa-l uploadez sau incerc alta metoda...?

[•astronomy]

S-a pus la un moment dat o limita pe dimensiunea sursei 128 sau 256kb nu mai stiu exact, dar oricum sub 534kb

[•azotlichid]

Mai bine te gandesti la o rezolvare fara constante (care iti va fi cu siguranta folositoare si in viitor) 

[•devilkind]

si cea cu constante poate fi folositoare, la urma urmei dak arunci o privire pe sursa lui mihai patrascu de la oni 2002 la problema sumdiv ai sa vezi un vector de constate de 9901 elemente. Oricum u ai cam exagerat la faza asta cu 78498 constante.

[•filipb]

Nu am precalculat...doar ca am declarat un vector cu 78498 de constante

Daca tu ai precalculat numerele prime, poti sa faci fara constante in O(NlogN) folosind ciurului lui Eratostene.

[•jdv]

Ok...mersi de sfaturi...

O sa folosesc altceva atunci...