HDU 1058 Humble Numbers (DP)
1311 ワード
考え方:
2,3,5,7の4つの数でHumble Numbersを構築した.
dp[]配列で格納される数については、事前に表を打つ.
ACコード:
2,3,5,7の4つの数でHumble Numbersを構築した.
dp[]配列で格納される数については、事前に表を打つ.
ACコード:
#include<stdio.h>
int dp[5843];
int n;
int Min(int a,int b,int c,int d)
{
if(a<=b&&a<=c&&a<=d)return a;
else if(b<=a&&b<=c&&b<=d)return b;
else if(c<=a&&c<=b&&c<=d)return c;
else return d;
}
int main()
{
int i;
int t2,t3,t5,t7;
int t;
dp[1]=1;
t2=t3=t5=t7=1;
for(i=2;i<=5842;i++)
{
t=Min(2*dp[t2],3*dp[t3],5*dp[t5],7*dp[t7]);
if(t==2*dp[t2])t2++;
if(t==3*dp[t3])t3++;
if(t==5*dp[t5])t5++;
if(t==7*dp[t7])t7++;
dp[i]=t;
}
while(scanf("%d",&n)!=-1&&n)
{
if(n%10==1&&n%100!=11)printf("The %dst humble number is %d.
",n,dp[n]);
else if(n%10==2&&n%100!=12)printf("The %dnd humble number is %d.
",n,dp[n]);
else if(n%10==3&&n%100!=13)printf("The %drd humble number is %d.
",n,dp[n]);
else printf("The %dth humble number is %d.
",n,dp[n]);
}
return 0;
}