Baze-problema

[•Florian]

Salutare! M-am gandit putin la problema asta, insa nu`i pot gasi o rezolvare concreta! Suna kam asa:

*Exista numere care au proprietatea ca se scriu in doua baze diferite, prin trei cifre identice. De exemplu, numarul 273 (baza 10) in baza 9 se scrie 333 (9), si in baza 16 se scrie 111 (16). Concepeti un program care sa determine toate numerele mai mici ca N care au aceasta proprietate.

M-am gandit, si am obtinut ceva de genu` k cea mai mare baza posibila pt acest lucru ar fi ceva de genu` : Bmax=(sqrt(4*N-3)-1)/2  , insa nu`mi dau seama de o implementare concreta...

[•sima_cotizo]

Mi se pare ca stiu problema... nu a fost data undeva?

Anyway, nu ai specificat nimic de baza maxima pe care o putem considera... desi avand in vedere ca e vorba de 3 cifre identice, putem face o precalculare desteapta... zic si eu...

Cred ca daca descoperi ca sunt multe numere de acest gen (desi nu cred), poti sa limitezi intr-un fel memoria or smth... anyway, succes! 

[•devilkind]

aa sunt numai 9 numere cu 3 cifre identice 111, 222,333 ... 999. Ptr aceste numere iei il consideri ca fiind in baza i (i<= BMAX) si vezi dak e mai mic decat n sau nu. Complexitatea ar fi O(BMAX). dar ink nu stiu exact cat de mare poate fi

[•filipb]

Numerele nu sunt doar cele spuse de tine. Pot fi de exemplu si AAA, BBB, CCC, DDD, EEE, FFF ( in baza 16 ). Unde ai intalnit problema?
Pentru a afla toate numerele <= N care indeplinesc proprietatea ta, trebuie sa incerci toate bazele <= sqrt(N) ( e evident din scrierea dintr-o baza in alta, la scrierea de 3 cifre o sa iti apara baza la patrat ). Poti incerca sa iei baza i si baza j, sa scrii AAA in baza i = BBB in baza j, A cifra in baza i, B cifra in baza j. Poti afla toate rezultatele ( ecuatie de gradul 2 in i de parametru j ) si vezi care este mai mic decat N.

Complexitatea: Sa zicem ca ai fixat o baza j, j <= sqrt N. Acum trebuie sa fixezi si cealalta baza i < j,  si sa fixezi cifra C in baza j ( adica sa ai numarul CCC in baza j - si ramane de vazut daca exista pentru i, j, C fixate o alta cifra C1 a. i. C1C1C1 in baza i = CCC in baza j ). Acum:
complexitate = O(suma(j * j), j <= sqrtN) deci = O((sqrtN)^3) = O(N * sqrt N), de constanta 2 / 6 = 1/3.
 
Pentru N <= 30.000 merge lejer.

[•Florian]

Unde ai intalnit problema?

Mi se pare ca stiu problema... nu a fost data undeva?

Anyway, nu ai specificat nimic de baza maxima pe care o putem considera... desi avand in vedere ca e vorba de 3 cifre identice, putem face o precalculare desteapta... zic si eu...

Problema a fost data, in cate stiu eu la un concurs in Lugoj in 2001, insa nu mai stiu exact unde am vazut-o. Referitor la baza maxima nu era nicio restrictie. Am calculat ceva de genu:

*consider numarul de forma p= xxx (in baza b). In baza 10 arata asa: p=x*(b^2) +x*b+x. Stim ca p este mai mic decat N  si scotand factor comun pe x => x(b^2 +b+1)<=N. Sigur ca x>=1 rezulta ca b^2+b+1-N<=0. De aici avem o ecuatie de gradul 2, pe care o rezolvam si deducem ca b<=(sqrt(4*N-3)-1)/2. Asadat baza maxima ar fi Bmax=(sqrt(4*N-3)-1)/2. Si banuiesc ca o rezolvare se leaga tot de baza 10, din moment ce am aflat asta...