136  Ugly Numbers
Moderator: Board moderators

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

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7: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!
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!

 Learning poster
 Posts: 90
 Joined: Sat Feb 15, 2003 1:39 am
 Location: Paris, France
 Contact:
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.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.
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 .
Not AC yet AC at last
O(n^2)
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.
The Answer
859963392
But just for test, not for AC purpose!!!!![/b]
But just for test, not for AC purpose!!!!![/b]
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.
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.
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.
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
136 WA
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]
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*/

 Experienced poster
 Posts: 187
 Joined: Wed Dec 11, 2002 2:03 pm
 Location: Mount Papandayan, Garut
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
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?

 Guru
 Posts: 584
 Joined: Thu Jun 19, 2003 3:48 am
 Location: Sanok, Poland
 Contact:
136 in Scheme :)
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
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
(definemacro (consstream head tail) `(cons (delay ,head) (delay ,tail)))
(define (streamcar s) (force (car s)))
(define (streamcdr s) (force (cdr s)))
(define emptystream '())
(define streamnull? null?)
(define (conststream c) (consstream c (conststream c)))
(define (streamref s n)
(if (= n 0)
(streamcar s)
(streamref (streamcdr s) ( n 1))))
(define (streammap s f)
(if (streamnull? s)
emptystream
(consstream (f (streamcar s)) (streammap (streamcdr s) f))))
(define (scalestream s c)
(streammap s (lambda(x) (* x c))))
(define (streammerge s1 s2)
(cond ((streamnull? s1) s2)
((streamnull? s2) s1)
(else
(let ((x1 (streamcar s1))
(x2 (streamcar s2)))
(cond ((< x1 x2) (consstream x1 (streammerge (streamcdr s1) s2)))
((< x2 x1) (consstream x2 (streammerge s1 (streamcdr s2))))
(else (consstream x1 (streammerge (streamcdr s1) (streamcdr s2)))))))))
(define s (consstream 1 (streammerge (streammerge (scalestream s 2) (scalestream s 3)) (scalestream s 5))))
(streamref s 1499)

 Guru
 Posts: 584
 Joined: Thu Jun 19, 2003 3:48 am
 Location: Sanok, Poland
 Contact:
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, 100000th 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 300000th 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.
Actually, as I said before, this is my precalcutaion program. Does anyone have faster one?
And, by the way, could you count the 300000th 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.

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