-
Notifications
You must be signed in to change notification settings - Fork 1
/
UglyNumber.cpp
75 lines (62 loc) · 1.62 KB
/
UglyNumber.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/*************************************
* Ugly Numbers > UVa - 136
* solved by - (DP) Dynamic Programming
* @author Amirul Islam (shiningflash)
************************************/
#include <cstdio>
#include <iomanip>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <sstream>
#include <stack>
#include <list>
#include <iostream>
#include <assert.h>
/**Define memory set function**/
#define mem(x,y) memset(x,y,sizeof(x))
#define CLEAR(x) memset(x,0,sizeof(x))
/**Define function and object**/
#define pb push_back
#define Sort(v) sort(v.begin(),v.end())
#define _sort(s, n) sort(s, s+n)
#define sqr(x) ((x)*(x))
/**Define constant value**/
#define le 5001
#define ERR 1e-9
#define pi (2*acos(0))
#define PI 3.141592653589793
/**Define input**/
#define scanint(a) scanf("%d",&a)
#define scanLLD(a) scanf("%lld",&a)
typedef unsigned long ll;
using namespace std;
/**********************End*******************/
ll min3(ll a, ll b, ll c) {
return min(min(a, b), c);
}
ll getUGLY(int n) {
ll ugly[n], nxtUGLY = 1;
ll i2 = 0, i3 = 0, i5 = 0;
ll mul2 = 2, mul3 = 3, mul5 = 5;
ugly[0] = 1;
for (ll i = 1; i < n; i++) {
nxtUGLY = min3(mul2, mul3, mul5);
ugly[i] = nxtUGLY;
if (nxtUGLY == mul2) i2++, mul2 = ugly[i2] * 2;
if (nxtUGLY == mul3) i3++, mul3 = ugly[i3] * 3;
if (nxtUGLY == mul5) i5++, mul5 = ugly[i5] * 5;
}
return nxtUGLY;
}
int main() {
cout << "The 1500'th ugly number is " << (ll) getUGLY(1500) << ".\n";
return 0;
}