OJ Board

Posted: **Mon Jan 07, 2008 12:20 pm**

Recently, I met an interesting problem, I don't know whether VOJ has a similar problem.

V = 2^i * 3^j * 5^k
i, j, k all belong to natural number, i.e. , 0, 1, 2...
so, V can be 1, 2, 3, 4, 5, 6, 8, 9, 10,..... in ascending order.
Input is n, which represents the order number of V
Output is the value of V.

Sample Input
7
Sample Output
8
=============================================

Well, I've got an idea which is simple but has low efficiency.
The benefit of this idea is no need to consider the ascending order, but
there're so many invalid numbers need to be checked, such as 7 11 13
17 19...
So I wonder if there's a rule, by which V varies in ascending order with
i,j,k. Then we can only consider i, j, k, and n, without invalid V values.

Code: Select all

int main(void)
{
	int N;
	while(scanf("%d", &N)){
		if(N <= 0) continue;
		int v, p, temp;
		v = 1; p = 1;
		while(p < N){
			v++;
			temp = v;
			while(temp % 2 == 0) temp /= 2;
			if(temp == 1) { p++; continue;}
			while(temp % 3 == 0) temp /= 3;
			if(temp == 1) { p++; continue;}
			while(temp % 5 == 0) temp /= 5;
			if(temp == 1) { p++; continue;}
		}
		printf("%d\n", v);
	}
	return 0;
}

Has anybody got a smart idea, thanks!

Posted: **Mon Jan 07, 2008 2:02 pm**

Here is a similar problem
136-Ugly Numbers.

A better way of doing it is..

Let a1 a2 a3 ... an be the first n such numbers.
Then the (n+1)th number has to be the min( ai*2, aj*3, ak*5) where 1 <= i,j,k <=n and ai*2, aj*3 and ak*5 are the smallest numbers just greater than an.

Or you can generate all the numbers recursively, provided you know the upper limit of the Nth value.

Posted: **Mon Jan 07, 2008 10:34 pm**

This common method is known as "moving pointers" method.
(Excuse me for my bad english

)

Posted: **Tue Jan 08, 2008 9:19 am**

sohel, thank u very much, u enlightened me:)

I use bisearch to find the first one in a1-an
which larger than an/2, supposing it's ai
which larger than an/3, supposing it's aj
which larger than an/5, supposing it's ak

then an+1 is min{2*ai, 3*aj, 5*ak}

Posted: **Sun Apr 27, 2008 9:33 am**

think about i+j+k=C
let C=1,2,3,...
for C=1,
(I,J,K)=(1,0,0),(0,1,0),(0,0,1)
then C=2,
(I,J,K)=(1,1,0),(1,0,1),(0,1,1),(2,0,0),(0,2,0)),(0,0,2)
sort above sequence ,and go on.C=3

Posted: **Sun Apr 27, 2008 9:38 am**

sorry,my answer is wrong.
listen the others...

Posted: **Tue Dec 27, 2011 7:45 pm**

lotoren wrote:sohel, thank u very much, u enlightened me:)

I use bisearch to find the first one in a1-an
which larger than an/2, supposing it's ai
which larger than an/3, supposing it's aj
which larger than an/5, supposing it's ak

then an+1 is min{2*ai, 3*aj, 5*ak}

I give thanks to lotoren and recursively to Sohel bhai.

Posted: **Tue Mar 10, 2015 1:33 pm**

Then the (n+1)th number has to be the min( ai*2, aj*3, ak*5) where 1 <= i,j,k <=n and ai*2, aj*3 and ak*5 are the smallest numbers just greater than an. ???

OJ Board

V = 2^i * 3^j * 5^k, how 2 work out the problem efficiently?

V = 2^i * 3^j * 5^k, how 2 work out the problem efficiently?

Re: V = 2^i * 3^j * 5^k, how 2 work out the problem efficiently?

Re: V = 2^i * 3^j * 5^k, how 2 work out the problem efficiently?

Re:

Re: V = 2^i * 3^j * 5^k, how 2 work out the problem efficien