首页 > 代码库 > poj 1338
poj 1338
Ugly Numbers
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 20697 | Accepted: 9193 |
Description
Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, ...
shows the first 10 ugly numbers. By convention, 1 is included.
Given the integer n,write a program to find and print the n‘th ugly number.
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, ...
shows the first 10 ugly numbers. By convention, 1 is included.
Given the integer n,write a program to find and print the n‘th ugly number.
Input
Each line of the input contains a postisive integer n (n <= 1500).Input is terminated by a line with n=0.
Output
For each line, output the n’th ugly number .:Don’t deal with the line with n=0.
Sample Input
1290
Sample Output
1210
Source
New Zealand 1990 Division I,UVA 136
#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<cmath>#include<algorithm> #include<cstdlib>using namespace std;int n,dp[1600],i,j,m;int MIN(int a,int b,int c){a=min(a,b);return min(a,c);}int main(){dp[1]=1,i=1,j=1,m=1;for(int k=2;k<=1500;k++){dp[k]=MIN(dp[i]*2,dp[j]*3,dp[m]*5);if(dp[k]==dp[i]*2) i++;if(dp[k]==dp[j]*3) j++;if(dp[k]==dp[m]*5) m++;}while(scanf("%d",&n),n)printf("%d\n",dp[n]);return 0;}
poj 1338
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。