Advertisement
Ishtiaq

Untitled

Oct 14th, 2014
3,335
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include <cstring>
  5. #include <string>
  6. #include <cctype>
  7. #include <stack>
  8. #include <queue>
  9. #include <list>
  10. #include <vector>
  11. #include <map>
  12. #include <sstream>
  13. #include <cmath>
  14. #include <bitset>
  15. #include <utility>
  16. #include <set>
  17. #define INT_MAX 2147483647
  18. #define INT_MIN -2147483648
  19. #define pi acos(-1.0)
  20. #define N 1000000
  21. #define long long LL
  22. using namespace std;
  23.  
  24. int ugly[1501];
  25.  
  26. int main()
  27. {
  28.     int p2,p3,p5,a,b,c;
  29.     ugly[1] = p2 = p3 = p5 = 1;
  30.     for(int i=2; i < 1501 ; i++){
  31.  
  32.         a = 2* (ugly[p2]);
  33.         b = 3* (ugly[p3]);
  34.         c = 5* (ugly[p5]);
  35.  
  36.         if(a<b && a<c ){
  37.             ugly[i] = a;//insert value
  38.             p2++;//increase p2
  39.         }
  40.         else if(b<a && b<c ){
  41.             ugly[i] = b;//insert value
  42.             p3++;//increase p2
  43.         }
  44.         else if(c<a && c<b ){
  45.             ugly[i] = c;//insert value
  46.             p5++;//increase p2
  47.         }
  48.         else if(a == b){
  49.             p3++;
  50.             i--;//decrease i as not inserted
  51.         }
  52.         else if(a == c){
  53.             p5++;
  54.             i--;
  55.         }
  56.         else if(b == c){
  57.             p5++;
  58.             i--;
  59.         }
  60.     }
  61.     //output
  62.     cout << "The 1500'th ugly number is " << ugly[1500] << "." << endl;
  63.  
  64.     return 0 ;
  65. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement