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

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

Post by Almost Human » Wed Apr 23, 2003 12:40 pm

is it trully 42 ?

how can it be ? isn't it should be thousands may be greater .. ?

Eric
Learning poster
Posts: 83
Joined: Wed Sep 11, 2002 6:28 pm
Location: Hong Kong

Post by Eric » Wed Apr 23, 2003 1:37 pm

Yes~ :roll:

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed Apr 23, 2003 1:37 pm

Nah, I just couldn't resist.

You don't seriously think anyone would give you the answer?
Then you could just print it and there would be no more fun.

Let me put it this way: if you count up by one every second, it would take you some 27 years and 3 months to reach the answer. Considerably less than the 7,500,000 years it took Deep Thought to come up with the answer 42!

bery olivier
Learning poster
Posts: 90
Joined: Sat Feb 15, 2003 1:39 am
Location: Paris, France
Contact:

Post by bery olivier » Sat Apr 26, 2003 4:39 pm

little joey wrote:You don't seriously think anyone would give you the answer?
Then you could just print it and there would be no more fun.
If somebody really want to get accepted that way, it's really easy to write a brute force algorithm just to get the answer and then print it. But who can be proud of such a code.
Anyway, the solution is probably already written in others topics. Even the source is somewhere else. Everyone can send it. He/She will get one more problem accepted (very impressive :-? ) and can only get for this problem 1900th with 0:00.000/64 :wink: .
Not AC yet Image AC at last Image

paulhryu
New poster
Posts: 45
Joined: Sat Jan 26, 2002 2:00 am
Contact:

O(n^2)

Post by paulhryu » Thu May 01, 2003 7:17 am

Especially when a very simple O(n^2) algorithm exists, as well as some more complex ones that run faster. But we're taking sub .1 second times here.

Zhao Le
Learning poster
Posts: 80
Joined: Mon May 05, 2003 4:09 am
Location: Shanghai,China

The Answer

Post by Zhao Le » Thu May 08, 2003 8:28 am

859963392
But just for test, not for AC purpose!!!!![/b]

Hisoka
Experienced poster
Posts: 120
Joined: Wed Mar 05, 2003 10:40 am
Location: Indonesia

Post by Hisoka » Thu May 08, 2003 2:18 pm

hello...

I think for test your algo correct or not, you can try to solve problem "humble number " http://acm.uva.es/p/v4/443.html both of them can be solved with same algorithm.

epsilon0
Experienced poster
Posts: 112
Joined: Tue Nov 12, 2002 11:15 pm
Location: Paris, France.

Post by epsilon0 » Fri May 09, 2003 8:09 am

a nice variant of this problem would be to make the number of prime factors variable.
the input would look like:

2
2 3
100

4
3 11 31 37
222

etc...

i'm sure it would heat some brains.
We never perform a computation ourselves, we just hitch a ride on the great Computation that is going on already. --Tomasso Toffoli

if11026
New poster
Posts: 3
Joined: Mon Jun 30, 2003 5:39 am
Contact:

136 WA

Post by if11026 » Thu Jul 03, 2003 7:13 am

What is wrong with my code ?
can anybody tell me ? I think I've missunderstood the problem..

[c]/* UGLY NUMBER */

#include <stdio.h>

#define true 1
#define false 0
#define boolean unsigned int

boolean IsPrime (int x);
/* Determine if x is a prime number or not*/

boolean Is235 (int x);
boolean IsExistOther (int x);
int main()
{
int ctr, i, j,bil;

ctr = 0;
bil = 1;

clrscr();
while (ctr < 1500)
{
if ((Is235(bil)) || (bil == 1))
{
if (bil == 1)
{

ctr++;
bil++;
}
else if (IsExistOther (bil))
{
bil++;
}
else
{

ctr++;
bil++;
}
}
else
{
bil++;
}
}

printf("The 1500'th ugly number is : %d", bil );


return 0;
}

boolean IsPrime (int x)
{
int cprime, i;

if (x == 1)
{
return true;
}
else
{
cprime = 0;
for (i=1; i<= x ; i++ )
{
if (x % i == 0)
{
cprime++;
}
}
if (cprime == 2)
{
return true;
}
else
{
return false;
}
}
}

boolean Is235 (int x)
{
return ((x % 2 == 0) || (x % 3 == 0) || (x % 5 == 0));
}

boolean IsExistOther (int x)
{
int i, error;

error = 0;
for (i = 1; i<= x ;i++ )
{
if ( x % i == 0)
{
if ((IsPrime(i)) && ((i!= 2) || (i!= 3) || (i != 4)))
{
error++;
}
}
}
if (error == 0)
{
return true;
}
else
{
return false;
}
}[/c]
/* IF ITB*/

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Thu Jul 03, 2003 3:35 pm

i didnt check completely your code, since i dont have compiler here. but there are several things that you should notice..
1. do not need to use clrscr
2. check your output and compare it with the sample output in the problem description. there are two mistakes.
3. i think you misunderstood about prime factors, or perharps you write wrong code. and also notice that its only prime factors is 2, 3 and 5.
hope it can help and good luck.

titid
Kalo mau kaya, buat apa sekolah?

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

136 in Scheme :-)

Post by Krzysztof Duleba » Mon Jul 28, 2003 8:44 pm

Hi!

With a task like that one I really regret we can't submit solutions in Lisp/Scheme. Look at the code: isn't it just beautiful? Of course, I looked up the right answer with it and made a valid c++ program, but it's not the same :-)
There is the Bigloo, which can be used as a converter from Scheme to C, but unfortunalety I don't think it is available during ACM contests :-)

Code: Select all

(define-macro (cons-stream  head tail) `(cons (delay ,head) (delay ,tail)))
(define (stream-car s) (force (car s)))
(define (stream-cdr s) (force (cdr s)))

(define empty-stream '())
(define stream-null? null?)

(define (const-stream c) (cons-stream c (const-stream c)))

(define (stream-ref s n)
  (if (= n 0)
      (stream-car s)
      (stream-ref (stream-cdr s) (- n 1))))

(define (stream-map s f)
  (if (stream-null? s)
      empty-stream
      (cons-stream (f (stream-car s)) (stream-map (stream-cdr s) f))))

(define (scale-stream s c)
  (stream-map s (lambda(x) (* x c))))

(define (stream-merge s1 s2)
  (cond ((stream-null? s1) s2)
        ((stream-null? s2) s1)
        (else
         (let ((x1 (stream-car s1))
               (x2 (stream-car s2)))
           (cond ((< x1 x2) (cons-stream x1 (stream-merge (stream-cdr s1) s2)))
                 ((< x2 x1) (cons-stream x2 (stream-merge s1 (stream-cdr s2))))
                 (else (cons-stream x1 (stream-merge (stream-cdr s1) (stream-cdr s2)))))))))

(define s (cons-stream 1 (stream-merge (stream-merge (scale-stream s 2) (scale-stream s 3)) (scale-stream s 5))))

(stream-ref s 1499)

Master
Learning poster
Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm
Location: St. Johns, Canada
Contact:

Post by Master » Tue Jul 29, 2003 9:12 am

This is a simple problem. you have to make output only one thing. So you use just make a precalculation and then just make the output.

so Simpleeeeeeeee........ :lol:

Master
Learning poster
Posts: 82
Joined: Thu Oct 10, 2002 1:15 pm
Location: St. Johns, Canada
Contact:

Post by Master » Tue Jul 29, 2003 9:29 am

just use precalculation and then print te rsult

my precalculation program tooks 42 min of time to get the result

i got AC

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

Post by Krzysztof Duleba » Tue Jul 29, 2003 1:19 pm

And what if I tell you that the code runs for 0.1 s to get the right answer and it could easily count, lets say, 100000-th ugly number in 10s. time limit?

Actually, as I said before, this is my precalcutaion program. Does anyone have faster one? ;-)

And, by the way, could you count the 300000-th ugly number in 15s.? If you do, we can compare our results, mine is here:

62864273786544799804687500000000000000000000000000000000 :-)

All I did to get it was to change 14999 into 299999 in my code. Nothing else was necessary.

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

Post by Krzysztof Duleba » Tue Jul 29, 2003 1:21 pm

Oh, now I see that your code was running for 42 min. to solve the problem for 1500-th ugly number. Can you see the difference? ;-)

Post Reply

Return to “Volume 1 (100-199)”