infoarena

Fie A multimea tuturor numerelor naturale de forma 2^x * 3^y * 5^z cu x,y,z=0,1,2,....
Aflati si afisati primele N elemente ale  multimii A in ordine crescatoare.

Complexitate: O(N).

Imi da si mie cineva o idee?

Deci stai sa inteleg : primul element al multimii o sa fie 2 * 3 * 5, al doilea 2² * 3² * 5² si tot asa ?

Nu!
Primul element este 1=2⁰ * 3⁰ * 5⁰.
Oricum nu stiu cat de relevant este.
Algoritmul banuiesc ca este acelasi:-?.

Ar veni 2⁰*3⁰*5⁰ apoi 2¹*3⁰*5⁰,2⁰*3¹*5⁰ , 2²*3⁰*5⁰ , 2⁰*3⁰*5¹ , 2¹*3¹*5⁰.
Daca ar fi cum spuneti voi sarcina ar trebui sa fie 2^x*3^x*5^x,x=0,1,2.

Primele 8 numere sunt:
1; 2; 3; 4; 5; 6; 8; 9 adica 2⁰*3⁰*5⁰, 2¹*3⁰*5⁰,2⁰*3¹*5⁰ , 2²*3⁰*5⁰ , 2⁰*3⁰*5¹ , 2¹*3¹*5⁰...

Nu este aceiasi putere pentru 2,3,5 ci sunt puteri diferite.

Vom genera solutia intr-un vector (sa zicem V), care la final va avea primele N elemente ale multimii in ordine sortata.
Bineinteles V[ 1 ] = 1; Vom dori sa generam vectorul deja in ordine crescatoare, asa ca vom tine trei pointeri (p1, p2, p3) cu urmatoarea semnificatie (sa presupunem ca pana acum am generat primele K elmente):
p1 = cel mai mic element din V care inmultit cu 2 este mai mare decat V[ k ]
p2 = cel mai mic element din V care inmultit cu 3 este mai mare decat V[ k ]
p3 = cel mai mic element din V care inmultit cu 5 este mai mare decat V[ k ].

Asadar la pasul K, luam minimul dintre (V[p1] * 2, V[p2] * 3, V[p3] * 4), il trecem la pozitia V[K + 1] si incrementam pointerul corespunzator maximului.

Bineinteles ca inital p1 = p2 = p3 = 1;

Sper ca este ok solutia si explicatia.


Problema nu s-a dat la admitere la Informatica la Unibuc?

@parvu: la pointerii aia cred ca vroiai sa zici cel mai mic element din V care inmultit cu X (X = 2, 3, 5) sa fie mai mare decat V[k]. Cum ai zis tu toti pointerii ar fi pe V[k].

@tibi: da, ai dreptate, am modificat

In primul rand multumesc pentru raspuns.
In al doilea rand nu trebuie sa selectez minimul dintre (V[p1] * 2, V[p2] * 3, V[p3] * 4)?
In al treilea rand, este de la admiterea de anul acesta de la Unibuc dar problema mi s-a parut familiara(sigur nu exista pe infoarena sau pe campion mai degraba:-? ) insa nu-mi aduc aminte s-o fi facut.
Probabil doar am citit-o si negasind solutia am lasat-o balta.

Da iei minimul, parvu asta e cam neatent :)
Eu parca sa zic ca am vazut-o la o nationala pe la gimnaziu.

Da, sunt cam neatent  :P. Daca dadeam admitere la Unibuc, probabil nu intram  :D

Intrai. :P Ultima medie la buget a fost 5.45.

Cred ca am avut-o eu la OJI intr-a 8-a :). OJIGim 2008 cred...

Asta este problema lui Hamming (sau sirul lui Hamming) care nu are legatura cu distanta Hamming. E ceva mentionat pe aici:
http://en.wikipedia.org/wiki/Regular_number