443 - Humble Numbers

[soyoja]

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]

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]

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]

You can't use // in ANSI C. (there might be others, but this is the first one I notice..)

[tat tvam asi]

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]

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]

can someone put many, a lot, ouputs for compare or send to my mail thanks

[mahabubcse]

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]

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]

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.

[jagadish]

numbers ending 11 should be suffixed with 'th' not 'st'

[Minilek]

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]

[jagadish]

please remove your source codes. this forum shouldn't become a solution manual to the problem archive in the long run

[jhonny_yang]

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]

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 !!