136 - Ugly Numbers

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

PerHagen
New poster
Posts: 23
Joined: Thu Oct 14, 2004 1:45 am
Location: lima

Post by PerHagen » Mon Jan 24, 2005 8:41 pm

:-? 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

Post by neno_uci » Mon Jan 24, 2005 10:59 pm

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. :D

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

136-why PE

Post by 59557RC » Sun Apr 10, 2005 4:27 pm

#include<stdio.h>

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

return 0;}
aaa

User avatar
mohiul alam prince
Experienced poster
Posts: 120
Joined: Sat Nov 01, 2003 6:16 am
Location: Dhaka (EWU)

Post by mohiul alam prince » Sun Apr 10, 2005 4:44 pm

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

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Sun Apr 10, 2005 4:46 pm

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

Post by byerlan » Thu Apr 28, 2005 7:02 am

:evil:
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??

Post by KvaLe » Mon May 02, 2005 8:09 am

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);
} 
Giorgi Lekveishvili

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

Post by KvaLe » Mon May 02, 2005 8:23 am

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 by KvaLe » Mon May 02, 2005 6:14 pm

Post here what this function is doing :wink:.
Giorgi Lekveishvili

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

Post by byerlan » Tue May 03, 2005 8:36 am

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

Post by KvaLe » Tue May 03, 2005 8:27 pm

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 :wink:.
Giorgi Lekveishvili

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

Post by byerlan » Wed May 04, 2005 8:35 am

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

Post by KvaLe » Wed May 04, 2005 4:59 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.

Post by Gaolious » Thu Jun 23, 2005 12:31 am

( 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
New poster
Posts: 2
Joined: Tue Jun 28, 2005 10:01 pm

Post by mikeboulos » Wed Jul 06, 2005 10:03 pm

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

Post Reply

Return to “Volume 1 (100-199)”