Humble Numbers

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 14364 Accepted Submission(s): 6236

Problem Description

A number whose only prime factors are 2,3,5 or 7 is called a humble number. The sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 24, 25, 27, ... shows the first 20 humble numbers.

Write a program to find and print the nth element in this sequence

Input

The input consists of one or more test cases. Each test case consists of one integer n with 1 <= n <= 5842. Input is terminated by a value of zero (0) for n.

Output

For each test case, print one line saying "The nth humble number is number.". Depending on the value of n, the correct suffix "st", "nd", "rd", or "th" for the ordinal number nth has to be used like it is shown in the sample output.

Sample Input

1 2 3 4 11 12 13 21 22 23 100 1000 5842 0

Sample Output

The 1st humble number is 1.

The 2nd humble number is 2.

The 3rd humble number is 3.

The 4th humble number is 4.

The 11th humble number is 12.

The 12th humble number is 14.

The 13th humble number is 15.

The 21st humble number is 28.

The 22nd humble number is 30.

The 23rd humble number is 32.

The 100th humble number is 450.

The 1000th humble number is 385875.

The 5842nd humble number is 2000000000.

　　题意：求出给定范围里面的因子内只包含1,2,3,5,7的所有数(只需要找前面5842个)。

　　做法如下：由于第5842个数是2000000000，所以不能从1~2000000000逐个检验是不是符合要求，因此我们可以之直接按顺序构造出这5842个数，打个表保存在数组里面查找就可以了。这里用的思想是DP，方法是在已知的Humble Numbers里面滚动着来生成新的数，这很符合DP的思想，用已知的条件不断从未知中推出更多的已知。用四个变量作为四个指针，从第一个元素开始，求出第一个数与2、3、5、7的积，然后从中求出最小的一个作为新的Humble Numbers，当然有可能会出现一个新的Humble Numbers由2、3、5、7中两个以上的数同时相乘得到，因此在移动指针的时候要判断4次，可能会有指针会在同一次循环里面移动，这样才可以保证不会有相同的数出现。

　　总的来说这一题的做法对于现在的我来说挺有创造性，更不如说现在的自己因为从前的一时不小心理解错了ACM，现在的下意识里经常都是想一题怎样将模板往上面套，但是明明自己知道这是不对的，还是不自觉地做了起来，大概是这样，自己的思维开始狭窄，所以，现在要改变这种想法，如果ACM的各种问题真的可以直接套模板的话，那就变得没意思了，那就变得跟考试没有区别，那还举办这种比赛有什么用呢？(以上是一时想到的东西，顺便记下来→_→)。

上代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #define min(x,y) (x<y ? x : y)
 4 #define minp(a,b,c,d) (min(min(a,b),min(c,d)))
 5 #define MAX (5842+2)
 6 using namespace std;
 7 
 8 int dp[MAX];
 9 
10 void deal(){
11     int n=MAX-2;
12     int i1,i2,i3,i4;
13     int t1,t2,t3,t4;
14     memset(dp,0,sizeof(dp));
15     dp[1]=1;
16     i4=i3=i2=i1=1;
17     for(int i=2;i<=n;i++){
18         t1=dp[i1]*2;
19         t2=dp[i2]*3;
20         t3=dp[i3]*5;
21         t4=dp[i4]*7;
22         dp[i]=minp(t1,t2,t3,t4);
23         if(t1==dp[i]) i1++;
24         if(t2==dp[i]) i2++;
25         if(t3==dp[i]) i3++;
26         if(t4==dp[i]) i4++;
27     }
28     //puts("BUG!");
29 }
30 
31 int main()
32 {
33     int n;
34     deal();
35     while(scanf("%d",&n),n){
36         printf("The %d",n);
37         if(n%10==1 && n%100!=11) printf("st");
38         else if(n%10==2 && n%100!=12) printf("nd");
39         else if(n%10==3 && n%100!=13) printf("rd");
40         else printf("th");
41         printf(" humble number is %d.
",dp[n]);
42     }
43     return 0;
44 }

1058