## 443 - Humble Numbers

Moderator: Board moderators

sam83
New poster
Posts: 1
Joined: Sat Jan 31, 2009 4:22 pm

#include<iostream>
#include<vector>
#include<math.h>
using namespace std;
int main()
{
long long int a,b=0,c,i,j,k,l;
vector<long long int>v;
for(i=0;i<=31;i++){
for(j=0;j<=31;j++){
for(k=0;k<=31;k++){
for(l=0;l<=31;l++){
a=pow(2,l)*pow(3,k)*pow(5,j)*pow(7,i);
if(a>0)
v.push_back(a);
}
}
}
}
sort(v.begin(),v.end());
while(cin>>a){
b++;
if(a==0)
break;
if(b!=1)
cout<<endl;
cout<<"The "<<a;
if(a%100==11 || a%100==12 || a%100==13)
cout<<"th ";
else if(((a%100)/10)==1)
cout<<"th ";
else if((a%10)==1)
cout<<"st ";
else if((a%10)==2)
cout<<"nd ";
else if((a%10)==3)
cout<<"rd ";
else
cout<<"th ";

cout<<"humble number is "<<v[a-1]<<".";
}
return 0;
}

kawsar
New poster
Posts: 12
Joined: Thu Aug 05, 2010 7:40 pm

#include<stdio.h>
#include<math.h>
#include<stdlib.h>

void InsertionSort(long m[], long n){
long i, k, key;

for(k=2;k<=n;k++){
key = m[k];
i=k-1;

while(i>0 && m>key){
m[i+1]=m;
i--;
}
m[i+1]=key;
}
}

int main(){
long i, j, k, l, n ;
long a ;
double x ;

n = 0 ;
for(i=0; i<31; i++){
for(j=0; j<20; j++){
for(k=0; k<14; k++){
for(l=0; l<12; l++){
x = pow(2,i) * pow(3,j) * pow(5,k) * pow(7,l) ;
if(x <= 2000000000)
a[++n] = x ;
}
}
}
}

InsertionSort(a, n);

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

j = n % 10 ;
i = n % 100 ;

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

return 0;
}

elmagnifico
New poster
Posts: 5
Joined: Mon Apr 30, 2012 10:15 am

Got acc.. Try out cases like.. 111,211... If it's a problem with suffixes this is most likely where all f us make mistakes.
Last edited by elmagnifico on Mon Apr 30, 2012 9:57 pm, edited 1 time in total.

masum93
New poster
Posts: 7
Joined: Wed May 11, 2011 11:15 am

Firstly I have some suggestions. Use the code

Code: Select all

``[code]``
[/code] tag above to post codes. Otherwise it is really hard to understand codes.
Use some spaces and indentetion in appropriate places, so that the code remains readable. If you alone understand your code, it is not going to help you a lot, right? For example, you can give a line space between declaring library and functions.
Better if you use ideone or pastebin instead of direct copy pasting codes here.
Now, back to your code, it seems that you are generating humble numbers every time you are taking inputs, which is I think unnecessary. Just generate them once and store them in an array to use later. Also, you should run the while loop with the condition i < MAX where MAX is the maximum limit of given input. Also there are some matters of prefixes like st, nd etc. Handle them properly. They caused me WA as well once. Also, for safety, it is better to use MAX+10 or MAX+something. You can declare array of 5850 here. That won't cause you a MLE. Also, it is good to declare arrays globally.

panhantao
New poster
Posts: 2
Joined: Tue Aug 14, 2012 6:00 pm

For those who are confused about "st","nd","rd","th":

if a number n ends with 11 or 12 or 13 (in other words, if(n%100==11 || n%100==12 || n%100==13) ),the suffix would be "th"
otherwise, if n ends with 1(n%10 == 1), its suffix would be "st", ends with 2,"nd" and ends with 3, "rd".

Here are some tests:

Code: Select all

``````511
512
513
514
601
632
653
677
800
``````

Code: Select all

``````The 511th humble number is 35721.
The 512th humble number is 35840.
The 513th humble number is 36000.
The 514th humble number is 36015.
The 601st humble number is 61236.
The 632nd humble number is 72030.
The 653rd humble number is 81000.
The 677th humble number is 91875.
The 800th humble number is 165888.
``````

Laevatein
New poster
Posts: 2
Joined: Wed Feb 13, 2013 3:40 am

what's wrong with my code?

Code: Select all

``````#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <map>
using namespace std;

vector<long> humble;
map<long,bool> sudah;

void generate(long n)
{
if (!sudah[n])
{
humble.push_back(n);
sudah[n] = true;
if (n <= 1000000000) generate(n*2);
if (n <= 666666666) generate(n*3);
if (n <= 400000000) generate(n*5);
if (n <= 285714285) generate(n*7);
}
}

int main()
{
generate(1);
sort(humble.begin(),humble.end());
long n;
scanf("%ld",&n);
while (n)
{
printf("%The %ld",n);
if(n % 100 >= 11 && n% 100 <= 13)
printf("th ");
else
if (n % 10 == 1) printf("st ");
else
if (n % 10 == 2) printf("nd ");
else
if (n % 10 == 3) printf("rd ");
else
printf("th ");
printf("humble number is %ld.\n",humble[n-1]);
scanf("%ld",&n);
}
return 0;
}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Don't print the %
Check input and AC output for thousands of problems on uDebug!

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm