136 - Ugly Numbers

[PerHagen]

i don't understand the problem ...this is my wrong!!
THx OMega

[neno_uci]

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]

#include<stdio.h>

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

return 0;}

[mohiul alam prince]

Hi
use this
printf("The %lu'th ugly number is %lu\n",n,un);
instead of this
printf("The %lu'th ugly number is %lu",n,un);

MAP

[Krzysztof Duleba]

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]

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;

[KvaLe]

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 [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);
} 

[KvaLe]

I accepted it. I thought that I must print all ugly numbers with index from 1 to 1500 .

[KvaLe]

Post here what this function is doing .

[byerlan]

Rezult of F(x) is equal to count of numbers
that are ugly and less or equal to x.

[KvaLe]

To solve this problem use DP.
I solved it with this algor.:
Let first K ugly number is U [1] ... 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 .

[byerlan]

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.

[KvaLe]

I solved it and it didn't got TL.

[Gaolious]

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

[mikeboulos]

I thought the same thing so what are we supposed to do