136  Ugly Numbers
Moderator: Board moderators
136why PE
#include<stdio.h>
int main(void)
{unsigned long n = 1500 , un=********;
printf("The %lu'th ugly number is %lu",n,un);
return 0;}
int main(void)
{unsigned long n = 1500 , un=********;
printf("The %lu'th ugly number is %lu",n,un);
return 0;}
aaa

 Experienced poster
 Posts: 120
 Joined: Sat Nov 01, 2003 6:16 am
 Location: Dhaka (EWU)

 Guru
 Posts: 584
 Joined: Thu Jun 19, 2003 3:48 am
 Location: Sanok, Poland
 Contact:
136  4e za prikol
what is wrong with this function
i want to find how many ugly numbers less or equal to 'x'...
Function F(x : LongInt) : LongInt;
var x2,x3,x5 : LongInt;
cnt,T : Int64;
i,j,k : LongInt;
Begin
x2 := trunc(Ln(x)/Ln(2));
x3 := trunc(Ln(x)/Ln(3));
x5 := trunc(Ln(x)/Ln(5));
cnt := 0;
For i := 0 to x2 do
For j := 0 to x3 do
For k := 0 to x5 do Begin
T := int64(trunc(exp(Ln(2)*i)));
T := T*int64(trunc(exp(Ln(3)*j)));
T := T*int64(trunc(exp(Ln(5)*k)));
if T <= x then cnt := cnt+1;
end;
F := cnt;
end;
I am not as clever as you might think about me...
P136 WA. Why??
Hi.
My solution on P136 gets WA.
Can anyone help me?
Here is my solution:
My solution on P136 gets WA.
Can anyone help me?
Here is my solution:
Code: Select all
#include <stdio.h>
#include <stdlib.h>
double K, A [1600];
double Min (double A, double B) { return A < B ? A : B; }
int main (void) {
/* freopen ("output.txt", "w", stdout); */
long I, J;
double M;
A [0] = 1;
printf ("The 1500'th ugly number is");
for (I = 0; I < 1500; I++) {
M = A [I];
K = 2000000000;
for (J = I; J >= 0 && 5*A [J] > M; J) {
if (2*A [J] > M) K = Min (K, 2*A [J]);
if (3*A [J] > M) K = Min (K, 3*A [J]);
K = Min (K, 5*A [J]);
}
A [I+1] = K;
printf (" %.0f", A [I]);
}
printf (".\n");
exit (0);
}
Giorgi Lekveishvili
Thank you, but this one works O(1500^2) isn't it. What is the time you got on AC for this task, could you tell me? I wanted to find that with Binary search using F(x). And I did it!!! Thank you. I even didn't think about DP for this question. And I will be able to solve this like question using your method. Thank you for New Ideas.
GL.
GL.
I am not as clever as you might think about me...

 New poster
 Posts: 28
 Joined: Mon Nov 04, 2002 8:03 pm
 Location: South Korea, Seoul
 Contact:
hm.
( 2 * x )
or
( 3 * y )
or
( 4 * z )
<= 1500
prepare.
x = 1, y = 1, z = 1 and the STACK[0] = 1
first.
STACK[1] number is smallest number in ( 2*x ), ( 3*y), ( 4*z ) .
you can found it ( 2 * x ) when x = 1 ; it is smallest number ;
so, STACK[1] = 2 .
and next number is must be larger then 2
so, set x=2, y=1 and z=1.
x=2, y=1, z=1
the next number is y=1 ( 3 ) > STACK[3] , y= 2.
.....
1
2
3
4
6
...
......
or
( 3 * y )
or
( 4 * z )
<= 1500
prepare.
x = 1, y = 1, z = 1 and the STACK[0] = 1
first.
STACK[1] number is smallest number in ( 2*x ), ( 3*y), ( 4*z ) .
you can found it ( 2 * x ) when x = 1 ; it is smallest number ;
so, STACK[1] = 2 .
and next number is must be larger then 2
so, set x=2, y=1 and z=1.
x=2, y=1, z=1
the next number is y=1 ( 3 ) > STACK[3] , y= 2.
.....
1
2
3
4
6
...
......

 New poster
 Posts: 2
 Joined: Tue Jun 28, 2005 10:01 pm