136 - Ugly Numbers
Moderator: Board moderators
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]
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]
-
- A great helper
- Posts: 284
- Joined: Thu Feb 28, 2002 2:00 am
- Location: Germany
- Contact:
There isn't "the" correct process. You sound a little bit as if there's only one approach to solve the problem.taj79 wrote: Is this the correct process?
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).
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.
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.
-
- A great helper
- Posts: 284
- Joined: Thu Feb 28, 2002 2:00 am
- Location: Germany
- Contact:
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.
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, you are using the board in a right way. =)
If the following is your output:
Final hint: try to compare your answer, i.e. the above sentence, CHARACTER BY CHARACTER to that of the sample output.
If the following is your output:
I can tell you that your answer DIFFERS from the correct answer, what's different is not the value you computed.The 1500'th ugly number is 859963392 .
Final hint: try to compare your answer, i.e. the above sentence, CHARACTER BY CHARACTER to that of the sample output.
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.
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.
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.

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.
-
- A great helper
- Posts: 284
- Joined: Thu Feb 28, 2002 2:00 am
- Location: Germany
- Contact:
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...
Last edited by Stefan Pochmann on Wed Jun 19, 2002 5:19 am, edited 1 time in total.