## 136 - Ugly Numbers

Moderator: Board moderators

PerHagen
New poster
Posts: 23
Joined: Thu Oct 14, 2004 1:45 am
Location: lima i don't understand the problem ...this is my wrong!!
THx OMega
hello !

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba
Hi PerHagen:

In this problem you must find the 1500th ugly number and print it.

Ugly numbers are numbers which are only divisible by 2, 3, 5, that is 2^a*3^b*5^c.

Did you get it??? Read the problem carefully and you will understand.

Hope it helps...

Yandry. 59557RC
New poster
Posts: 26
Joined: Sun Mar 20, 2005 9:28 pm
Contact:

### 136-why PE

#include<stdio.h>

int main(void)
{unsigned long n = 1500 , un=********;
printf("The %lu'th ugly number is %lu",n,un);

return 0;}
aaa

mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)
Hi
use this
printf("The %lu'th ugly number is %lu\n",n,un);
printf("The %lu'th ugly number is %lu",n,un);

MAP

Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:
P.E. stands for Presentation Error. It happens when your solution doesn't conform to output specification, but apart from that the result is fine.

In this case you're obviously missing an end of line at the end of the output.

byerlan
New poster
Posts: 3
Joined: Tue Mar 29, 2005 1:45 pm
Location: Kazakhstan

### 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...

KvaLe
New poster
Posts: 30
Joined: Sun May 01, 2005 7:45 pm

### P136 WA. Why??

Hi.
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 ;

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  = 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

KvaLe
New poster
Posts: 30
Joined: Sun May 01, 2005 7:45 pm
I accepted it. I thought that I must print all ugly numbers with index from 1 to 1500 .
Giorgi Lekveishvili

KvaLe
New poster
Posts: 30
Joined: Sun May 01, 2005 7:45 pm
Post here what this function is doing .
Giorgi Lekveishvili

byerlan
New poster
Posts: 3
Joined: Tue Mar 29, 2005 1:45 pm
Location: Kazakhstan
Rezult of F(x) is equal to count of numbers
that are ugly and less or equal to x.
I am not as clever as you might think about me...

KvaLe
New poster
Posts: 30
Joined: Sun May 01, 2005 7:45 pm
To solve this problem use DP.
I solved it with this algor.:
Let first K ugly number is U  ... U [K].
For all I (1..K) M = Min3 (2*U , 3*U , 5*U )
and U [K+1] = Min (M (I = 1..K)).

GL .
Giorgi Lekveishvili

byerlan
New poster
Posts: 3
Joined: Tue Mar 29, 2005 1:45 pm
Location: Kazakhstan
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.
I am not as clever as you might think about me...

KvaLe
New poster
Posts: 30
Joined: Sun May 01, 2005 7:45 pm
I solved it and it didn't got TL.
Giorgi Lekveishvili

Gaolious
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 = 1

first.
STACK 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 = 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 , y= 2.

.....

1
2
3
4
6
...
......

mikeboulos
New poster
Posts: 2
Joined: Tue Jun 28, 2005 10:01 pm
I thought the same thing so what are we supposed to do