#include<iostream>

using namespace std;

class Solution {
public:
    int nthUglyNumber(int n) {
        if(!n) return 0;
        vector<int> ans(n,0);
        int i = 0,j = 0,k = 0;
        ans[0] = 1;
        for(int idx = 1;idx<n;idx++)
        {
            int temp = min(ans[i]*2,min(ans[j]*3,ans[k]*5));
            if(temp == ans[i]*2)i++;//最小的++
            if(temp == ans[j]*3)j++;
            if(temp == ans[k]*5)k++;
            ans[idx] = temp;
        }
        return ans[n-1];
    }
};

int main()
{
    return 0;
}