003 Fractii

[•wefgef]

http://infoarena.ro/Ciurul-lui-Erathostene

[•sima_cotizo]

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.

Parca ciurul din articol e O(N) [ adica O(sqrt(N) * sqrt(N) )] ... plus o parcurgere a intregului sir unde marchezi daca e prim sau nu [ inca O(N) ]... L-am inteles eu gresit? 

[•peanutz]

Eu am o alta problema. Nu inteleg de ce vector de constante, eu la precalculari folosesc vector normal. Nu-mi explica si mie careva care e treaba? Va rog

[•devilkind]

pai cred ca nu precalcula programul acele nr prime. Cred ca si-a facut un progam separat care a scris in sursa programului sau
const int prime[9901] = {2,3,5,7,11 bla bla bla}

astfel a obtinut si acea marime astronomica a sursei. La urma urmei asa poti sa rezolvi aproape orice problema de pe infoarena facand un back care sa iti calculeze rezultatu ptr n luand valori de la 1 la nmax si sa iti scrie apoi in sursa unui alt program a[ x ]=rez; x - o valoare intre 1 si nmax iar rez fiind rezultatul intors de back ptr valoarea x . Ce idee smekera )

[•peanutz]

Mi-e clar ca si-a generat nr prime cu un alt program. Intrebarea mea e de ce const int? Ce ar avea mai special? ...sau e doar asa de 'fitze'

[•devilkind]

sincer sa fiu nush dak e vreun avantaj la memorie sau timp, doar ca dak il declari const int atunci zona de memorie va fi read only dar cum am mai zis nush dak ofera vreun avantaj.

[•k_ounu_eddy]

am si eu o intrebare.cum se pun constantele alea in sursa?ca doar nu introduci 78498 numere prime manual?sau le ati luat din fisierul ala cu primele 100000 numere prime?

[•azotlichid]

Daca tii neaparat sa iti declari un vector de constante, poti sa iti faci un program care sa iti genereze respectiva bucata de cod. Oricum, la concursuri nu vei avea de unde altundeva sa iti iei fisiere cu numere prime.
Cu toate astea e de preferat (pentru eleganta si simplitate) sa iti construiesti vectorul de numere prime direct in sursa cu un ciur micut care se implementeaza in cateva linii 

[•k_ounu_eddy]

si cum faci programelul ala?nu,eu am facut problema ,dar intreb asa ca fapt divers.

[•filipb]

Pur si simplu faci un program care sa genereze numerele prime si sa le scrie intr-un fisier oarecare ( cu , intre ele eventual), si le copii din fisierul respectiv in codul tau sursa.

[•Darth_Niculus]

si cum faci programelul ala?nu,eu am facut problema ,dar intreb asa ca fapt divers.

   Ceea ce nu vad ce rost are.... poti sa faci ciurul si in programul tau, nu e nevoie sa il faci seaparat si sa faci constanta si etc.....

[•devilkind]

de fapt adrian vladu cred ca se referea sa faci un program care sa iti scrie direct in codu sursa: a[1]=2;a[2]=3;a[3]=5 bla blabla
Adik ceva de genu un program care sa iti scrie programu.

[•k_ounu_eddy]

Am inteles.

[•Adix]

Am facut problema fractiilor , imi merge pentru cazurile prezentate anterior (in afara de cel cu 1000000000 pt ca folosesc borland) si imi da raspuns gresit la 4 din teste, la restul luand TLE .. care ar putea fi problema ? folosesc ciurul si numarul de fractii il calculez  folosind

Cod:

i->n 
        2*(tot(i))+1 

[•llucky]

well si eu am incercat dupa cum scriati pe forum, am implementat ciurul lui erathostene si functia totiene, si pentru toate exemplele date in problema si de voi pe forum obtin raspunsul corect. la teste totusi, primesc 9 TLE-uri... vreo idee ce sa mai optimizez la algoritm? sunt sigur ca e o chichitza ce nu vad eu... aveti vreo idee ce as putea face?

[•dodgerblue]

O intrebare :
este posibil sa apara erori daca atribui unei variabile de tip long long int valoarea unei variabile de tip float inmultita cu o variabila de tip int? (nu stiu prea multe despre g++. in borland c nu am probleme).

[•Darth_Niculus]

 N-ai probleme.... dar rezultatul o sa fie int evident.... desi ar fi de preferat sa folosesti asa:

Cod:

 float a;
 int b,rez;
 rez=((int)a) * b;

[•skyel]

mie imi face toate exe bine, dar incepe sa crape p undeva p unde n depasiste 100.000, any ideeas?

[•sima_cotizo]

Aloci vreun vector mai mic decat trebuie? ... in windows mai crapa cand accesezi memorie unde nu trebuie... in linux crapa sigur

[•skyel]

aloc un vector char de Nmax unde Nmax e 1000010 (sa fiu sigur k nu aloc prea mult)
LE: Sursa e scrisa in BC 3.1 si e compilata cu gnu (as fi scris-o in rhide, dar tot nu imi dau seama de ce nu vrea sa creeze fisier d tip object), deci nu prea pot sa fac debug pt n>65000

[•sima_cotizo]

Puteai sa o scrii si in notepad, conteaza doar unde o compilezi ...

Ok, daca nu iti iese din vector, detaliaza in ce sens "crapa" programul?...
Cateva probleme posibile:

• daca faci ceva recursiv (nu cred ca e nevoie in pr asta) iti "crapa" stiva;
• daca imparti la 0 ar trebui sa primesti FPE si sa crape
• daca aloci mai mult decat ai disponibil la un moment dat mi se pare ca iar face urat
• poate fi de la faptul ca nu ai compilat cum trebuie... (eu stiu, poate ai pus vreun flag care nu trebuia)

[•skyel]

prin a crapa ma refer la faptul k o ia rezultatu razna, adik nu da nici o eroare, si ceea ce nu inteleg e cum de imi da pt primele 100.000 de numere si pt restu pana la un mil incepe sa devieze.
LE: acuma imi da sigsegv..... 
LLE: solved sigsegv(era un for pt ciur kre incepea de la i*i si knd i era mai mare k 1000 imi iesea din vector), mai ramane doar partea cu rezultatul incorect

[•dodgerblue]

Am reusit cu problema  Nu credeam ca daca voi declara doi vectori de 1000000 de elemente de tip long long int, problema va rula, dar se pare ca am obtinut 100 de puncte!  Cum a spus cineva inaintea mea pe forum (nu mai stiu exact cine) e memorie "fara numar" 

[•Marius]

Nu, e "lafaiala"! 

[•dodgerblue]

Nu, e "lafaiala"! 

Asa  Scuze