1 #include <iostream>
   2 #include <sstream>
   3 #include <string>
   4 #include <algorithm>
   5 #include <vector>
   6 using namespace std;
   7 
   8 #define GI ({int _t; scanf("%d", &_t); _t;})
   9 #define FOR(i, a, b) for (int i=a; i<b; i++)
  10 #define REP(i, a) FOR(i, 0, a)
  11 template<class T> string toString(T n){ostringstream ost;ost<<n;ost.flush();return ost.str();}
  12 int toInt(string s){int r=0;istringstream sin(s);sin>>r;return r;}
  13 #define DBGV(_v) { REP(_i, _v.size()) { cout << _v[_i] << "\t";} cout << endl;}
  14 #define INF (int)1e10
  15 #define LIMIT 1500
  16 int main() {
  17 	int marker[3], num[3];
  18 	int value[LIMIT];
  19 	REP(i, 3) marker[i] = 0;
  20 	num[0] = 2; num[1] = 3; num[2] = 5;
  21 	REP(i, LIMIT) value[i] = 1;
  22 	FOR(i, 1, LIMIT) {
  23 		int cur = INF;
  24 		REP(j, 3) {
  25 			cur = min(cur, value[marker[j]]*num[j]);
  26 		}
  27 		value[i] = cur;
  28 		REP(j, 3) {
  29 			if (cur == value[marker[j]] * num[j]) {
  30 				marker[j]++;
  31 			}
  32 		}
  33 	}
  34 	printf("The 1500'th ugly number is %d.\n", value[LIMIT-1]);
  35 	return 0;
  36 }