## 443 - Humble Numbers

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

Moderator: Board moderators

soyoja
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:
In my opinion, this is a little faked problem. We must practice not English grammar or I/O format but algorithm and coding ability.
Some of UVA problem required annoying output format.
I think that it's not need for contestants.

Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela

### 443 in C compile error help

please help me i dont get why compile error in C!!!! anyway here is my source code, i used the compiler of red hat linux 9 gcc (i dont know the version) and the program run very well in my red hat please help.
if the helper can please tell me where is the error, the line, and the possible solution thanks.

[c]
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

int main(void)
{

int i,j,k,l,n;
double x;
char st;
int menor,aux;

double pdos[31],ptres[20],pcinco[16],psiete[13];
int general[5843];
x = (double)1;
st=(char *)malloc(sizeof(char)*2);
//get the powers of 2 = 2,4,8,16,32.....
for(i = 0; i < 31 ; i++){
pdos = x ;
x = x*2;
}
//get the powers of 3 = 3,9,27,81,.....
x = 1;
for(i = 0; i < 20 ; i++){
ptres = x ;
x = x*3;
}
//get the powers of 5 = 5,25,125,625,.....
x = 1;
for(i = 0; i < 16 ; i++){
pcinco = x ;
x = x*5;
}
//get the powers of 7 = 7,49,.....
x = 1;
for(i = 0; i < 13 ; i++){
psiete = x ;
x = x*7;
}
int p=0;
//then get all the possible combination
for(i = 0; i < 31 ; i++){
for(j = 0; j < 20 ; j++){
for(k = 0;k < 16 ;k++){
for(l = 0 ; l < 13 ; l++){
if(psiete[l]*pcinco[k] > 2000000000)
continue;
if(psiete[l]*pcinco[k]*ptres[j] > 2000000000)
continue;
if(psiete[l]*pcinco[k]*ptres[j]*pdos > 2000000000 )
continue;

general[p] = (int)pdos*ptres[j]*pcinco[k]*psiete[l];
p++;

}
}
}
}

// order the elements
// this algorithm is for order the elements in the array
for(i=0;i<5843-1;i++)
{
for(j=i+1,menor=i;j<5843;j++)
if(general[j]<general[menor])
menor=j;
aux=general;
general=general[menor];
general[menor]=aux;
}

k = 0;
while(1){
scanf("%d",&i);
if(i == 0)
break;
k = i%10;
if( (4<=i && i<=19) || (k == 0)){
st = "th";
}else{
switch(k){
case 1:
st = "st";
break;
case 2:
st = "nd";
break;
case 3:
st = "rd";
break;
default:
st = "th";
break;
}

}
printf("The %d%s humble number is %d \n",i,st,general);
}
return 0;
}[/c]

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA
Take a look at the following compile error message for your code.
678128.c: In function `main':
678128.c:18: warning: assignment makes integer from pointer without a cast
678128.c:19: parse error before `/'
678128.c:19: malformed floating constant
678128.c:20: warning: statement with no effect
678128.c:20: parse error before `)'
678128.c:16: warning: unused variable `general'
678128.c:15: warning: unused variable `psiete'
678128.c:15: warning: unused variable `pcinco'
678128.c:15: warning: unused variable `ptres'
678128.c:15: warning: unused variable `pdos'
678128.c:13: warning: unused variable `aux'
678128.c:13: warning: unused variable `menor'
678128.c:10: warning: unused variable `n'
678128.c:10: warning: unused variable `l'
678128.c:10: warning: unused variable `k'
678128.c:10: warning: unused variable `j'
678128.c:23: warning: control reaches end of non-void function
678128.c: At top level:
678128.c:24: parse error before `/'
678128.c:24: parse error at `..'
678128.c:28: warning: type defaults to `int' in declaration of `x'
678128.c:28: initializer element is not constant
678128.c:28: warning: data definition has no type or storage class
678128.c:29: parse error before `}'
678128.c:30: parse error at `..'
678128.c:34: warning: type defaults to `int' in declaration of `x'
678128.c:34: redefinition of `x'
678128.c:28: `x' previously defined here
678128.c:34: initializer element is not constant
678128.c:34: warning: data definition has no type or storage class
678128.c:35: parse error before `}'
678128.c:36: parse error at `..'
678128.c:40: warning: type defaults to `int' in declaration of `x'
678128.c:40: redefinition of `x'
678128.c:34: `x' previously defined here
678128.c:40: initializer element is not constant
678128.c:40: warning: data definition has no type or storage class
678128.c:41: parse error before `}'
678128.c:43: parse error before `/'
678128.c:55: warning: type defaults to `int' in declaration of `general'
678128.c:55: variable-size type declared outside of any function
678128.c:55: variable-sized object may not be initialized
678128.c:55: `pdos' undeclared here (not in a function)
678128.c:55: `i' undeclared here (not in a function)
678128.c:55: `ptres' undeclared here (not in a function)
678128.c:55: `j' undeclared here (not in a function)
678128.c:55: `pcinco' undeclared here (not in a function)
678128.c:55: `k' undeclared here (not in a function)
678128.c:55: `psiete' undeclared here (not in a function)
678128.c:55: `l' undeclared here (not in a function)
678128.c:55: warning: data definition has no type or storage class
678128.c:56: parse error before `++'
678128.c:73: warning: type defaults to `int' in declaration of `aux'
678128.c:73: `i' undeclared here (not in a function)
678128.c:73: warning: data definition has no type or storage class
678128.c:74: `i' undeclared here (not in a function)
678128.c:74: warning: type defaults to `int' in declaration of `general'
678128.c:74: conflicting types for `general'
678128.c:55: previous declaration of `general'
678128.c:74: `menor' undeclared here (not in a function)
678128.c:74: warning: data definition has no type or storage class
678128.c:75: `menor' undeclared here (not in a function)
678128.c:75: warning: type defaults to `int' in declaration of `general'
678128.c:75: conflicting types for `general'
678128.c:74: previous declaration of `general'
678128.c:75: warning: data definition has no type or storage class
678128.c:76: parse error before `}'
678128.c:78: warning: type defaults to `int' in declaration of `k'
678128.c:78: warning: data definition has no type or storage class
678128.c:79: parse error before `while'
678128.c:83: warning: type defaults to `int' in declaration of `k'
678128.c:83: redefinition of `k'
678128.c:78: `k' previously defined here
678128.c:83: `i' undeclared here (not in a function)
678128.c:83: warning: data definition has no type or storage class
678128.c:84: parse error before `if'
678128.c:103: parse error before string constant
678128.c:103: warning: type defaults to `int' in declaration of `printf'
678128.c:103: warning: data definition has no type or storage class
678128.c:75: storage size of `general' isn't known

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
You can't use // in ANSI C. (there might be others, but this is the first one I notice..)

tat tvam asi
New poster
Posts: 30
Joined: Sat Nov 30, 2002 1:04 pm
Helo Omega!

Gnu/linux and gcc is a good choice! If you
solve problems for uva, you have to compile
your sources with "-ansi" or better with
"-ansi -pedantic -Wall" option:
\$gcc -ansi -Wall -pedantic source.c
If you like // type comments , you can use the
cpp preprocessor with "-fpreprocessed" option:
\$cpp -fpreprocessed source.c source_for_uva.c
and then compile the "new" source as mentioned
above.
Another solution: simply use g++:
\$g++ -ansi -Wall source.c
and send the source.c as c++ source to uva.

hi,
Csaba.

ps.: the code will get wa.

Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela
Thanks for all the replies as you well know i am newbie and i used the compiler without that options mentioned before, and i want to know how i can get that message that get shamim ? if is the same options that said tat tvam asi and why wa ?

Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela
can someone put many, a lot, ouputs for compare or send to my mail thanks

mahabubcse
New poster
Posts: 1
Joined: Thu Jul 08, 2004 5:45 am
Contact:

### 443 humble number pls help me

i solved this problem . but i got time limit exit. i start loop from 1 to 2000000000. Can anyone tell me how can i skip or jump in this loop to reduce time?

TanveerAhsan
New poster
Posts: 5
Joined: Fri Oct 26, 2001 2:00 am
You can't run such a loop. It will take more than a minute (probably).

Generate all the numbers whose prime factors are 2, 3, 5, 7 and insert them in a sorted list like we do in insertion sort. For example, 1 is a humble number. Now multiply it with 2, 3, 5 and 7 and the new list will be 1 2 3 5 7. Next take the 2nd humble number i.e. 2 and multiply it with 2, 3, 5, and 7 and the new list will be 1 2 3 4 5 6 7 10 14. Now take 3 and repeat the process. Repeat the same as required.

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:
I have also done this problem but get WA. I tried my program on all their example inputs and it worked perfectly (their example inputs include 5842, 1000, and some other smaller numbers as well). Is there something I'm not seeing here?

[c]
gone
[/c]

I thought maybe it was the fact that I was using a long and needed something bigger..so I tried using a double but still got WA. It turns out long is big enough anyway since the 5842nd humble number is small enough to fit in a long.

Thanks.

PS: Tanveer, although your solution works I believe it runs in n^2 time (it's at least nlgn because of the inserting, but I think n^2 since you have to shift stuff over when you insert). If you're interested in an O(N) solution, check out the code 2 posts down.
Last edited by Minilek on Wed Aug 04, 2004 3:48 am, edited 2 times in total.

Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA
numbers ending 11 should be suffixed with 'th' not 'st'
if u can think of it .. u can do it in software.

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:
ya, thanks for the reply. just saw that a few minutes ago, and fixed it (also gotta change for numbers ending in 12 and 13 too to not be "nd" and "rd"). *sigh*...*shoots himself in the foot*

This code got AC:

[c]
AC
[/c]
Last edited by Minilek on Wed Aug 04, 2004 3:48 am, edited 1 time in total.

Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA
please remove your source codes. this forum shouldn't become a solution manual to the problem archive in the long run
if u can think of it .. u can do it in software.

jhonny_yang
New poster
Posts: 22
Joined: Fri Jan 17, 2003 8:24 am

### Cry for 443

Can Any body tell what is my wrong ?

[c]
#include <stdio.h>

unsigned long Min(long Hasil2, long Hasil3, long Hasil5, long Hasil7)
{
long Temp[4],max;
int i;

Temp[0]= Hasil2; Temp[1]=Hasil3; Temp[2]=Hasil5; Temp[3]=Hasil7;
max=Temp[0];
for (i=1;i<4;i++){
if (Temp<max){
max=Temp;
}
}
return max;
}

int main()
{
long ugly[5842];
int k = 5842;
long index2=0, index3=0, index5=0, index7=0;
long Hasil2, Hasil3, Hasil5,Hasil7,target;
long i;

Hasil2=1; Hasil3=1; Hasil5=1; Hasil7=1;
ugly[0]=1;

for (i=1;i<k;i++)
{
target=ugly[i-1]+1;
while((Hasil2 = 2 * ugly[index2]) < target) index2++;
while((Hasil3 = 3 * ugly[index3]) < target) index3++;
while((Hasil5 = 5 * ugly[index5]) < target) index5++;
while((Hasil7 = 7 * ugly[index7]) < target) index7++;
ugly = Min(Hasil2, Hasil3, Hasil5, Hasil7);
}

while (scanf("%ld",&i)){
if (i==0)break;

if ((i%100)>=10&&(i%100)<=20)printf("The %ldth humble number is %ld.\n",i,ugly[i-1]);
else if ((i%10)==1)printf("The %ldst humble number is %ld.\n",i,ugly[i-1]);
else if ((i%10)==2)printf("The %ldnd humble number is %ld.\n",i,ugly[i-1]);
else if ((i%10)==3)printf("The %ldrd humble number is %ld.\n",i,ugly[i-1]);
else if ((i%10)==4)printf("The %ldth humble number is %ld.\n",i,ugly[i-1]);
else printf("The %ldth humble number is %ld.\n",i,ugly[i-1]);
}

return 0;
}

//@END_OF_SOURCE_CODE [/c]

Ghust_omega
Experienced poster
Posts: 115
Joined: Tue Apr 06, 2004 7:04 pm
Location: Venezuela
Hi !! jhonny_yang i summit your code like you posted here and gives AC try to summit the source code on-line

Hope it Helps
Keep posting !!