136 - Ugly Numbers

10153EN · Post by **10153EN** » Sat Jun 15, 2002 3:28 pm

I am not sure. But something I just catch my attention.

You have generated 15^3 numbers by using the for loops.
Do you think that these 15^3 numbers are the 15^3 SMALLEST ugly numbers??

I don't think so. I think that 2^15 should be one of them.

taj79 · Post by **taj79** » Sat Jun 15, 2002 4:57 pm

i can increase from checking 15^3 numbers to more but how much should I do?

Is this the correct process?

10153EN · Post by **10153EN** » Sat Jun 15, 2002 5:10 pm

I don't think it's the correct one~ since your approach can only generate some, say n, but not the smallest n ugly numbers.

Instead, you can try generate all ugly numbers less than a limit, say 2 x 10^9.

You can do that by multiply a number by 2 if it's less than the limit; multiply a number by 3 if it's less than the limit; multiply a number by 5 if it's less than the limit.[/code]

Stefan Pochmann · Post by **Stefan Pochmann** » Sat Jun 15, 2002 11:59 pm

taj79 wrote: Is this the correct process?

There isn't "the" correct process. You sound a little bit as if there's only one approach to solve the problem.

Yes, yours will easily work if you make the exponents larger. Of course you will also produce some ugly numbers that are too large and therefore not really needed.

10153EN's tip to generate everything up to a limit can remove this waste. If you end up with fewer than 1500 ugly numbers, then you know your limit was too small and you just try it again with a larger limit.

Btw, there's a way to generate the first n ugly numbers in order with time and space O(n).

taj79 · Post by **taj79** » Mon Jun 17, 2002 7:28 pm

I did like this

for(r=0;r<25;r++)
for(q=0;q<80;q++)
for(p=0;p<300;p++)
{
u = ( pow(2,p)*pow(3,q)*pow(5,r) );
if(u > pow(2,1000) )
{/* printf("\n Exceeding\n"); */
continue; }
A[++t] = u;
}
My array size is 600000

i am getting answer 859963392
the judge says it is wrong.

what should i do?
I can't make the size (array) 2400000
On running it gives segmentation fault.

10153EN · Post by **10153EN** » Mon Jun 17, 2002 8:41 pm

You are nearly successful.

The last hint: try to check more carefully for your output with the sample output, some minor mistake would worth a WA.

taj79 · Post by **taj79** » Tue Jun 18, 2002 8:05 am

I still can't figure out the mistake.
Could any one please give me more hint.
What does WA means.?

Stefan Pochmann · Post by **Stefan Pochmann** » Tue Jun 18, 2002 8:14 am

RTFM: http://acm.uva.es/problemset/replies.html

Sorry, don't want to offend anybody, but this is really getting annoying and some people are wasting their time here and some newbies exploit this and just don't care. I already stopped reading threads about specific problems two days ago. Exception: it's a problem I remember and I'm interested in it.

BIG BIG hint: the number you posted earlier is correct, now read the problem description again.

taj79 · Post by **taj79** » Tue Jun 18, 2002 5:59 pm

Please don't feel that I m misusing the board.
U said that my answer is correct.
On running my prog i m getting the output as

The 1500'th ugly number is 859963392 .

But thejudge says that wrong answer .

Is my answer is truly correct?

10153EN · Post by **10153EN** » Tue Jun 18, 2002 6:20 pm

taj79, you are using the board in a right way. =)

If the following is your output:

The 1500'th ugly number is 859963392 .

I can tell you that your answer DIFFERS from the correct answer, what's different is not the value you computed.
Final hint: try to compare your answer, i.e. the above sentence, CHARACTER BY CHARACTER to that of the sample output.

taj79 · Post by **taj79** » Tue Jun 18, 2002 7:59 pm

I really can't see the difference.
I have submitted this prog:
Where's the diff between sample output and my output?
Please help me

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
void sort(int A[],int t,int u);
void quicksort(double A[],int p,int r);
int partition(double A[],int p,int r);

main()
{ int t=0,i;
double p,q,r,u,A[1000000];

/* printf("\n 2^1000 = %.0f",pow(2,1000) );
u = ( pow(2,300)*pow(3,200)*pow(5,100) );
printf("\nu = %.0f",u);
if(u > pow(2,1000) )
printf("\n1");
else
printf("\n0");//exit(1);
printf("\n"); */
for(r=0;r<50;r++)
for(q=0;q<100;q++)
for(p=0;p<200;p++)
{
u = ( pow(2,p)*pow(3,q)*pow(5,r) );
if(u > pow(2,1000) )
{ /* printf("\n Exceeding\n"); */
continue; }
A[++t] = u;
/* if(t == 1)
A[1]= 1;
else
sort(A,t,u);
A[t]=u; */
/* if(A[t] < 0)
{ printf(" %d ",t);
exit(1);
} */
}
/* printf("t = %d\n",t);
printf("%.0f\n\n\n",A[t]);
printf("\n Before sorting: \n");
for(i=1;i<=1500;i++)
{ if(i%20 == 0)
printf("\n");
printf(" %.0f",A);
}
printf("\n\n\n\n\n Before entering quicksort\n\n"); */
quicksort(A,1,1000000);
/* printf("\n\n\n Exited quicksort\n\n");
printf("\n\n\n\n\n\n After sorting \n");
for(i=1;i<=1500;i++)
printf(" %.0f",A); */
/* printf("\n 1st number: %.0f",A[1]); */
printf("The 1500'th ugly number is %.0f.\n",A[1500]);
}

void quicksort(double A[],int p,int r)
{int q,count=0;
/* printf("\n\n Entered quicksort\n\n");
printf("p = %d r = %d\n",p,r); */
if(p<r){ ++count;
/* printf("%d",count); */
q = partition(A,p,r);
quicksort(A,p,q);
quicksort(A,q+1,r);
}
return;
}

int partition(double A[],int p,int r)
{ double x,u;
int i,j;
x = A[p];
i = p-1;
j = r+1;
while(1){
do{--j;
}while(A[j]>x);
do{ ++i;
}while(A<x);
if(i < j)
{ u = A ;
A= A[j];
A[j] = u;
}
else
return(j);
}
}

void sort(int A[],int t,int u)
{int y = t;
A[t] = u;
while(A[t] < A[t-1])
{
A[t] = A[t-1];
--t;
}
A[t]= u;
return;
}

Judge says
Your program has not solved the problem. It ran during 3.050 seconds.

10153EN · Post by **10153EN** » Tue Jun 18, 2002 8:38 pm

Hello~

Could you clear the comments and add the Code tags for your codes so that it's easier for us to read?

BTW, do you know there's a built-in function in C for quick sorting an array?

Mart · Post by **Mart** » Tue Jun 18, 2002 11:59 pm

I just cut and pasted your code and got AC (although it's not the quickest implementation in the world...

Are you sure you've set up the problem number correctly in the code?
i.e. a line like:

/* @JUDGE_ID: *yourID* 136 C */

Failing that it is probably a problem with your email. Try sending using a different email (especially if you are using something like hotmail).

Mart.

Stefan Pochmann · Post by **Stefan Pochmann** » Wed Jun 19, 2002 2:04 am

That's not quite correct, I believe? You did see a difference, because you removed the space before the ".". Btw, I just got your program accepted as is. Please read one of the many many other threads where email problems were already discussed...

taj79 · Post by **taj79** » Wed Jun 19, 2002 4:58 am

My solution finally got accepted.
I really don't know what was the mistake in my last submission.
Anyway,THANKS to all of you for helping me out with my silly mistakes.

Hey stefan,
what does BTW means?