首页 > 代码库 > poj 1338

poj 1338

2024-08-02 07:24:51   219人阅读

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. 

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


联系
我们