Commits

Martinho Fernandes  committed 15378e2

Solved 136: Ugly numbers

  • Participants
  • Parent commits fc40a35

Comments (0)

Files changed (5)

 /*
  * 100: The 3n + 1 problem
- * http://uva.onlinejudge.org/external/1/100.pdf
+ * http://uva.onlinejudge.org/external/1/100.html
  */
 
 #include <algorithm>
 /*
  * 101: The Blocks Problem
- * http://uva.onlinejudge.org/external/1/101.pdf
+ * http://uva.onlinejudge.org/external/1/101.html
  */
 
 #include <algorithm>
 /*
  * 102: Ecological Bin Packing
- * http://uva.onlinejudge.org/external/1/102.pdf
+ * http://uva.onlinejudge.org/external/1/102.html
  */
 
 #include <algorithm>
+/*
+ * 136: Ugly numbers
+ * http://uva.onlinejudge.org/external/1/136.html
+ */
+
+#include <algorithm>
+//#include <functional>
+#include <iostream>
+//#include <iterator>
+//#include <numeric>
+#include <vector>
+//#include <utility>
+using namespace std;
+
+class problem {
+public:
+    int solve(int n) {
+        vector<int> candidates;
+        candidates.reserve(1500);
+        candidates.push_back(1);
+        int p2, p3, p5;
+        p2 = p3 = p5 = 0;
+        for(int i = 1; i < n; ++i) {
+            int m2 = candidates[p2] * 2;
+            int m3 = candidates[p3] * 3;
+            int m5 = candidates[p5] * 5;
+            int m = min(min(m2, m3), m5);
+            candidates.push_back(m);
+            for(int j = p2; j <= i; ++j) {
+                if(candidates[j] * 2 > candidates.back()) {
+                    p2 = j;
+                    break;
+                }
+            }
+            for(int j = p3; j <= i; ++j) {
+                if(candidates[j] * 3 > candidates.back()) {
+                    p3 = j;
+                    break;
+                }
+            }
+            for(int j = p5; j <= i; ++j) {
+                if(candidates[j] * 5 > candidates.back()) {
+                    p5 = j;
+                    break;
+                }
+            }
+        }
+        return candidates.back();
+    }
+};
+
+int output(int n, int value) {
+    cout << "The " << n << "'th ugly number is " << value << "." << endl;
+}
+
+int main() {
+    problem p;
+    int ugly1500 = p.solve(1500);
+    output(1500, ugly1500);
+}
 /*
  * 591: Box of Bricks
- * http://uva.onlinejudge.org/external/5/591.pdf
+ * http://uva.onlinejudge.org/external/5/591.html
  */
 
 #include <algorithm>