Untitled

mail@pastecode.io avatar
unknown
c_cpp
a year ago
1.3 kB
15
Indexable
Never
#include <bits/stdc++.h> 
using namespace std;

struct Node {
    int val;
    int p;
    int q;
    
    Node (int _val, int _p, int _q) {
        val = _val;
        p = _p;
        q = _q;
    }
};

int solution(int N) {
    
    auto comparator = [] (Node *a, Node *b) {
        return a -> val > b -> val;
    };
    
    priority_queue<Node *, vector<Node *>, decltype(comparator)> pq(comparator);
    set<int> st;
    
    pq.push(new Node(1, 0, 0));
    st.insert(1);
    
    vector<int> seq;
    
    while (seq.size() <= N) {
        Node *nodePtr = pq.top();
        pq.pop();
        seq.push_back(nodePtr -> val);
        
        int exp_2 = nodePtr -> p;
        int exp_3 = nodePtr -> q;
        
        int next2SideVal = nodePtr -> val * 2;
        int next3SideVal = nodePtr -> val * 3;
        
        if (st.find(next2SideVal) == st.end()) {
            pq.push(new Node(next2SideVal, exp_2 + 1, exp_3));
            st.insert(next2SideVal);
        }
        
        if (st.find(next3SideVal) == st.end()) {
            pq.push(new Node(next3SideVal, exp_2, exp_3 + 1));
            st.insert(next3SideVal);
        }
    }
    
    return seq[N];
}


int main() {

    for (int i = 0; i <= 200; i++)
        cout << "A[" << i << "] = " << solution(i) << endl;

	return 0;
}