My solution of UVA 443 - Humble Numbers

443 - Humble Numbers

- Cannot use value-dp[], because 20000000000 > 32bit int and it is too large.
- Same reason, cannot use Eratosthenes Prime Number Sieve


- Notice how to generate 1st, 2nd, 111th, 221st etc... check both N%10 and N%100 (easy to miss N%100 part).



#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <list>


#define sz(k) (int)(k).size()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define forr(i,r) for(int i=0;i<r;i++)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define drep(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define nl(c) c<<endl;
#define db(cout,c) tr(c,it){cout<<" "<<*it;};nl(cout); 
#define inf24 (int)(1<<23-1)
#define inf32 (int)(1<<31-1)
#define inf64 (long long)(1LL<<63-1)
using namespace std;


int main(int argc, char *argv[])
{
    long long h[5844];
    h[1]=1LL;


    long long lim=1,hi=1,min;
    long long pt[]={2LL,3LL,5LL,7LL};
    rep(i,1,5844)
    {
        min=inf64;
        for(int j=i;j>=1;j--)
        {
            int k=0;
            for(;k<4;k++)
            {
                long long test=h[j]*pt[k];
                if(test<min&&test>lim)
                {
                    min=test;
//                    cout<<j<<","<<k<<"="<<min<<endl;
                }
            }
            if(h[j]*pt[3]<lim)break;
        }
        lim=h[i+1]=min;
//        cout<<"h["<<i+1<<"]="<<min<<endl;
    }
    
    int N,N10,N100;
    while(cin>>N)
    {
        if(N==0)break;
        string su;
        su="th";
        N10=N%10;
        N100=N%100;
        if(N10==1&&N100!=11)su="st";
        if(N10==2&&N100!=12)su="nd";
        if(N10==3&&N100!=13)su="rd";
        cout<<"The "<<N<<su<<" humble number is "<<h[N]<<"."<<endl;
    };
    return 0;
}