注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

告别迷茫

梦想与现实的差距,就是我们生活的意义。因为我们有差距,我们才会一直积累,在努力。

 
 
 

日志

 
 

HDU 1058 Humble Numbers  

2014-03-23 11:06:29|  分类: DP |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Humble Numbers

Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 12   Accepted Submission(s) : 9
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.
 

Source
University of Ulm Local Contest 1996
 

#include<stdio.h>

int cmp(int a,int b,int c,int d)
{
a = a > b ? b : a;
c = c > d ? d : c;
return a > c ? c : a;
}
int main()
{
int x[5842];
x[1]=1;
int i,a,b,c,d,n;
a=b=c=d=1;
for(i=2;i<=5842;i++)
{
x[i]=cmp(x[a]*2,x[b]*3,x[c]*5,x[d]*7);
if(x[i]==x[a]*2) a++;
if(x[i]==x[b]*3) b++;
if(x[i]==x[c]*5) c++;
if(x[i]==x[d]*7) d++;
}
while(scanf("%d",&n),n)
{
printf("The %d", n);
if(n%100 != 11 && n%10 == 1) printf("st");
else if(n%100 != 12 && n%10 == 2) printf("nd");
else if(n%100 != 13 && n%10 == 3) printf("rd");
else printf("th");
printf(" humble number is %d.\n", x[n]);
}
return 0;

}
/*
动态规划题,F[n] 可由2, 3, 5, 7与F[n-1]的乘积获得,取这四个数的的最小值,就是当前F[n]的值,即F[n] = min{F[n-1]*2, F[n-1]*3, F[n-1]*5, F[n-1]*7}。

  前6个数的递归过程:

n1 = 1;

  n2 = min{1*2, 1*3,1*5,1*7} = 2;

  n3 = min{2*2, 1*3, 1*5, 1*7} = 3;

  n4 = min{2*2, 2*3, 1*5, 1*7} = 4;

  n5 = min{3*2, 2*3, 1*5, 1*7} = 5;

  n6 = min{3*2, 2*3, 2*5, 1*7} = 6;
*/


  评论这张
 
阅读(5)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017