## 443 - Humble Numbers

Moderator: Board moderators

brunokbcao
New poster
Posts: 4
Joined: Sun May 14, 2006 4:22 pm
Location: Recife, PE
Contact:
TanveerAhsan wrote: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.

Yes... I used this method, and got accepted. There's a another way to do it:

int pos = 0;
int i, j, k, l

for (i = 0; i < limit; i++) {
for (j = 0; j < limit; j++) {
for (l = 0; l < limit; l++) {
for (m = 0; m < limit; m++) {
array[pos] = 2 ^ i * 3 ^ j * 5 ^ k * 7 ^ l; // 2 elevated to i, ...
pos++;
}
}
}
}

qsort(array, ...);

you can do it too. I don't tested if it gets and TLE Look at my status:
http://acm.uva.es/problemset/usersjudge.php?user=1754 Spykaj
New poster
Posts: 47
Joined: Sun May 21, 2006 12:13 pm

### 443 st nd rd th

char* end(int n){
if((n%100)/10==1)return "th";
if(n%10==1)return "st";
if(n%10==2)return "nd";
if(n%10==3)return "rd";
return "th";
}

printf("The %d%s humble number is %d.\n",n,end(n),T[n]);

Enjoy all and get AC thomas1016
New poster
Posts: 19
Joined: Mon May 29, 2006 4:12 pm

### 443 WA

why did it gave me WA it is alright while num<100?
it seems logically right ,did it?

Code: Select all

``````
#include <iostream>
#include <cmath>
using namespace std;
int check(int);

int main(void){
unsigned long long int k,a,pa;
while(cin>>k){
pa=0;
a=2000000100;
if(k==0){break;
}
cout<<"The "<<k;
switch(k%10)
{
case 1:
cout<<"st";
break;
case 2:
cout<<"nd";
break;
case 3:
cout<<"rd";
break;
default:
cout<<"th";
break;

}
cout<<" humble number is ";
while(check((a+pa)/2)!=k){
//cout<<"pa="<<pa<<"   "<<"a="<<a<<"   "<<(a+pa)/2<<" ans "<<check((a+pa)/2)<<endl;
if(check((a+pa)/2)>k){
// if(a!=(pa+a)/2){
a=(pa+a)/2;//}
// else{
//       a--;
//      }

}
else{
//   if(pa!=(pa+a)/2){
pa=(pa+a)/2;
//  }
//    else{
//         pa++;

//}

}

}
cout<<(a+pa)/2<<"."<<endl;

}

// system("pause");
return 0;
}
int check(int a){
int i,j,k,l,m;
m=0;
unsigned long long int q=1,w=1,e=1,r=1,y=1,t=1,u=1;

for(i=0,q=1;i<=log(a)/log(2);i++,q*=2){
for(j=0,w=1;j<=log(a)/log(3) && q*w<a;j++,w*=3){

for(k=0,e=1;k<=log(a)/log(5) && q*w*e<a;k++,e*=5){

for(l=0,r=1;l<=log(a)/log(7) && q*w*e*r<a;l++,r*=7){

m++;

}}}}

return m+1;
}

``````

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

input == 99,output should be 448
input == 98,output should be 441
input == 97,output should be 432

Yours produced :

Hope it helps... thomas1016
New poster
Posts: 19
Joined: Mon May 29, 2006 4:12 pm
Can U explain what lead to this result??? Giorgi
New poster
Posts: 48
Joined: Wed Jun 07, 2006 6:26 pm
Location: Georgia Tbilisi

I don't think that my solution is wrong and I can't understand why it
gives WA. I generate all numbers and then i print them.

Code: Select all

``````
var  a:array[1..5842] of int64;
i,j,n:longint;
k,p:int64;

procedure find(t:int64);

begin
for j:=i-1 downto 1 do
if (a[j]*t>k) then if (a[j]*t<p) then
p:=a[j]*t else else break;

end;

procedure make;
begin
a:=1; k:=1;
for i:=2 to 5842 do
begin
p:=maxlongint;
find(2);
find(3);
find(5);
find(7);
a[i]:=p; k:=p;
end;
end;

begin

make;
while n<>0 do
begin
write('The ',n);
if n = 11 then write('th') else if n=12 then write('th') else
if n = 13 then write('th') else
if n mod 10 = 1 then write('st') else if n mod 10=2 then write('nd')
else if n mod 10=3 then write('rd') else write('th');
writeln(' humble number is ',a[n],'.');
end;

end.

[/quote]``````
[/b]

Giorgi
New poster
Posts: 48
Joined: Wed Jun 07, 2006 6:26 pm
Location: Georgia Tbilisi
CAN ANYBODY HELP ME?????????????

albet_januar
New poster
Posts: 35
Joined: Wed Apr 12, 2006 6:03 pm
Location: jakarta, indonesia
Contact:
i don't know your code is correct or not, coz i dont know PASCAL..
but there is a bug in your code..

i think your code it will give 113 as '113rd', it should be '113th'..
i hope this will help u..

God Bless U..

Giorgi
New poster
Posts: 48
Joined: Wed Jun 07, 2006 6:26 pm
Location: Georgia Tbilisi
thank you very much, I got AC newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Contact:

thanx

got AC!
Last edited by newton on Tue Sep 05, 2006 2:27 pm, edited 1 time in total.

milacao
New poster
Posts: 5
Joined: Mon Aug 14, 2006 7:57 pm

Hi Newton,
I haven't tried yet this problem, but I see several things in your code:
1) GOTO: Although goto perhaps improves performance, it violates good structured programming conventions, so you should avoid it 2) With your loop, your code would fail if you have, i.e., number 2310, since it is a multiple of 2, 3, 5 and 7 (giving 'temp%a[j]==0' true), but not only, because it is also multiple of 11, so instead you should use something like:

while (temp%a[j] == 0) ...

but...
3) ... if you look at simple inputs and outputs, 5842nd humble number is 2000000000, so, to check this, you will have to do millions of divisions, and it is computationally really expensive.
I hope this helps,
Milacao.

jainal uddin
New poster
Posts: 6
Joined: Thu Jul 27, 2006 2:42 pm

### help me 443

Code: Select all

``````#include<stdio.h>
int main()
{

long long n,count,i,a,mod,h;
while((scanf("%lld",&n))!=EOF){
count=0;
for(h=1;count<n;h++)
{
a=h;

while(a%2==0)
a=a/2;

while(a%3==0)
a=a/3;

while(a%5==0)
a=a/5;

while(a%7==0)
a=a/7;
if( a == 1 )
count++;

}
mod=n%10;
if(mod==1)
printf("The %lldst humble number is %lld.\n",n,h-1);
else if(mod==2)
printf("The %lldnd humble number is %lld.\n",n,h-1);
else if(mod==3)
printf("The %lldrd humble number is %lld.\n",n,h-1);
else
printf("The %lldth humble number is %lld.\n",n,h-1);

}
return 0;
}

``````

jainal uddin
New poster
Posts: 6
Joined: Thu Jul 27, 2006 2:42 pm
hello try to make another algorithm to find out humble number.

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Contact:
jainal uddin wrote:hello try to make another algorithm to find out humble number.
Are you answering yourself!? ishtiaq ahmed
Learning poster
Posts: 53
Joined: Sat Jul 29, 2006 7:33 am
``````the code is removed after ac.