infoarena

Aici puteţi discuta despre problema Free (http://infoarena.ro/problema/free).

 Stie cineva un link unde gasesc operatii cu numere mari , ca la programu meu operatiile astea imi iau o gramada de timp?

da : http://info.devnet.ro/articole.php?page=art&art=22&artpage=4

mersi ffff mult cos_min . Intradevar erau cam complicate operatiile mele;  le faceam pe siruri de caractere (char) pt ca puteai sa afli lungimea lor dar se pare ca a fost o prostie. :D

hmm numa 20 pcte iau (restu TLE)... pt sqrt fac o cautare binara si operatiile pe nr mari le folosesc cele din articolul de pe info.devnet.ro
 :oops:

incearca sa extragi radicalul "ca pe foaie"... eu iau 70 pe rezolvarea asta, inca am un mic bug... si complexitate o sa iasa O(Nr cifre)...  :thumbup:

eu fac tot o cautare binara si operatiile de info.devnet  si iau 100

hmm dak initializez de fiecare data siru cu memset imi iese din timp shi dak nu ii il initializez nu imi merge ... ce pot face? need help

ca tot veni vorba de memset , stie cineva de ce la mine pe calculator nu merge NICIODATA memset-ul decat atunci cand initializez sirul cu 0 ??

memset-ul seteaza fiecare byte la valoarea pe care i-o dai. Pe un vector de char o sa-ti mearga mereu, dar pe un vector de int se seteaza atat primul cat si cel de-al doilea byte cu valoarea. De exemplu, facand memset(v, 1, sizeof(v)) unde v e char, fiecare element o sa fie egal cu 00000001, iar facand memset(v, 1, sizeof(v)) unde v e int, fiecare element o sa fie egal cu 0000000100000001.

Ma rog... asta daca sizeof(int) = 2. Daca sizeof(int) = 4... o sa apara 00000001 de 4 ori.

Singurele numere care isi pastreaza reprezentarea binara daca sunt dublate sunt -1 si 0 :) deci iti va merge si memset cu -1 tot timpul :)

memset(A, 0, sizeof(A)) va merge pe orice platforma daca A este de tipul char. daca A este de tip int sa spunem pot aparea surprize, in sensul ca toate elementele lui A nu vor avea valoarea 0 (zero). nu ar trebui sa fie nicio diferenta intre un for si memset, ba chiar sa mearga mai repede for-ul, insa pe un post mai vechi infoa erau facute niste teste si memset rula mai avantajos ca timp.
asa am auzit eu..   

Daca te refereai ca -1 e intreg, el are aceiasi reprezentare binara 111....111 pe oricati biti ar fi reprezentat, deci cred ca merge pe orice platforma la fel.

acuma m-am lamurit

hmm mai mult de 40 pcte nu pot scoate ...  :-s
nush ce sa modific la cautarea binara ... sigur acol ii ceva gresit

Uite aici doua tutoriale despre cautarea binara:
http://www.tbray.org/ongoing/When/200x/2003/03/22/Binary

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearch

Eu de cand am citit primul articol nu am mai bushit la cautare binara. Ideea e sa iti fixezi un invariant la inceput si atunci e foarte usor sa scrii codul fara sa te mai concentrezi la chestii de +/- 1 si sa nu fi sigur ce se intampla.

10x Cosmin ... mi-o iesit de 100 in sfarsit  \:D/ [am observat in al 2-lea articol o optimizare, care mo ajutat sa scot pctj maxim]

Ce optimizare ca sunt curios?

optimizare : mij=st+(dr-st)/2 .. dak am pus asta in loc de mij = (st+dr)/2 mi-o mers ...

dupa ce am facut cautarea binara, am observat ca implementarea ei pe numere HUGE dar intregi (fara virgula), obtine SQRT-ul doar pentru numerele patrate perfecte. De altfel asa e si logic 25*25 = 625 nu cu 626. Daca caut radical din 626 nu va gasi nimic.

O metdoda de a obtine truncul ar fi sa fac operatiile pe numere mari cu virgula. Dar inainte sa ma omor, poate exista o varianta mai simpla si nu-mi dau eu seama acuma.

Ma corectez... nu merge nici pe numere mari cu virgula

pai pentru fiecare mij vezi daca  (mij*mij <=nr&&(mij+1)*(mij+1)>n)
 atunci mij = sqrt(n)

mersi da deja imi dadusem seama. mersi oricum.

Dubios cos_mine :) aia nu prea e optimizare ci poate doar schimbare a modului in care scrii codul. O optimizare ar fi sa folosesti in loc de baza 10 o baza de 1000 sau 1000000.
Cat despre ce zice pocaitu nu tre sa faci (mij*mij <=nr&&(mij+1)*(mij+1)>n)
ci:
invariantul aici este ca low_end <= sqrt(n) si high_end > sqrt(n), vedeti ce usor stim ce valoare trebuie sa ii dam lui high_end si low_end dupa o comparatie, si nu mai apare nici un +-1.

poate lui cos_min ii dadea overflow..
adica poate st+dr iesea din tipul lui de date.. daca calculezi prin st+(dr-st)/2 nu vad unde poate da overflow
.. oricum, nu e optimizare :)

:) Nu prea poti vorbi la overflow la tipuri de date mari :).

nush ce ii .... da cu mij=(st+dr)/2 nu imi intra in timp shi cu mij=st+(dr-st)/2 ... 

Poate nu ai incercat cu ideea lui Mihai Patrascu.  8)

Am uitat sa pun link: http://info.devnet.ro/articole.php?page=art&art=22

Na, eu am scriu prima metoda care mi-a venit in cap si s-a dovedit buna . Mai totdeauna vor exista mai multe solutii la o problema.
Chiar si aici ar mai fi loc de ceva optimizari, dar nu prea si-ar mai avea rostul

he he ... hai k mi-o mers  :yahoo:

S-ar putea cand faci mij+1 iesi din intervalul in care faci cautarea binara si sa obtii rezultate neasteptate.

E important sa cititi cele doua articole pe care le-am zis mai devreme.

 in cazul de fata nu se intampla asta. adik, merge cu mij + 1

Vorbeam in general despre cum e frumos sa scrii o cautare binara si sa nu mai ai griji, sa nu te gandesti la cazuri. Da voi tot de cazuri imi ziceti  :fighting:. Ce sa ii faci :). Cum vreti voi :)

Ce frumos merge extragerea radacinii patrate daca reprezinti numarul in baza 2. Super.  :surf:

Cum se poate afla radicalu unui numar din reprezentarea numarului in baza 2?  :)

Probabil se refera la aflarea radicalului prin cautare binara (vezi ideea lui Mihai Patrascu de implementare). Cel putin de asta s-a vorbit in topic.

Cat va da pentru:
999192934845325420052052502005230001

MS mika ;)

999192934845325419052456116034709688

care e solutia pentru numere mari?

Pai... ai avea 2 alternative. Ori cauti binar rezultatul (pe numere mari... pentru fiecare m compari daca patratul lui m este mai mare sau mai mic decat numarul dat) sau faci radicalul ca pe foaie (pe asta nu'l mai stiu :-'). Spor  :)

Am incercat sa implementez radical de mana, cu cautarea binara a mers, dar iau incorect la testul 3 si 9. Care sa fie problema ? Am facut exact ca pe foaie, am trat orice caz particular.

pentru problema asta nu trebuie facuta descompunerea in factori primi a fiecarui factor?
adica avem  pasi:
1.descompunerea fiecarei celuli in parte
2.aflarea nr de divizori a nr descompus cu formula:
    nr div = (puterea_1_la_descompunere+1)*(puterea_2_la_descompunere+1)*...*(puterea_k_la_descompunere+1)
3.daca nr de div e par celula e inchisa,daca nu este deschisa

doar ca nu stiu cum sa fac o descompunere pe numere mari astfel incat sa intre in timp...

Raspunsul e N - radical(N). Trebuie implementata functia radical pe numere mari.

aaa acum am inteles :D multumesc mult pentru ajutor :)

o seara(noapte) buna :)

Merci de ajutor, am reusit oricum. E mult mai rapid implementat de mana decat cautarea binara.

Killed by signal 11(SIGSEGV) ???

Asta am vazut-o si eu. Doar ca am o problema: cum declar structura in care retin n-ul? n<10^100 => v[10000000...00] - pana la 100 de zero-uri  :-s :-s

n < 10 ^ 100 inseamna ca are maxim 100 cifre. Deci vectoru tau trebuie declarat v[101] minim, pentru ca fiecare element al lui va retine o cifra.

Mersi de raspuns, mi-am dat seama azi dimineata :oops: :aha:

Mie imi da Killed by signal 11 si nush de ce :aha: