FindTheMin

FindTheMin.cpp

#include <vector>
#include <map>
#include <set>
#include <algorithm>
#include <iostream>

#define FOR(i,a,b)                  for(int i=a;i<b;i++)
#define REP(i,a)                    FOR(i, 0, a)
#define all(a)                      a.begin(), a.end()
#define SORT(a)                     sort(all(a))
#define in(a,b)                     ( (b).find(a) != (b).end())
#define pb                          push_back
#define VI                          vector<int>

using namespace std;

inline bool is_looping(VI &nos, int k, int n){
    if(n - 1 - 2 *k < 0)
        return false;
    if(nos[n-k] != nos[n - 2 * k - 1])
        return false;
    for(int i = n-1; i >= n-k; i--){
        if(nos[i] != nos[i-k -1])
            return false;
    }
    return true;
}

int main(){
    int T;
    cin >> T;
    REP(tc, T){
        cout << "Case #" << tc + 1 << ": ";

        long long n, k, a, b, c, r;
        cin >> n >> k;
        cin >> a >> b >> c >> r;
        
        VI nos(10000000), counters(2*k, 0);

        nos[0] = a;
        if(nos[0] < 2 * k)
            counters[nos[0]]++;
        FOR(i, 1, k){
            nos[i] = (b * nos[i-1] + c) % r;
            
            // We keep track of all elements which are less than 2*k.
            // since we will not be inserting any element more than 2*k
            
            if(nos[i] < 2 * k)
                counters[nos[i]]++;
        }
        
        /* Set works like a heap */
        set<int> available;
        
        FOR(i, 0, 2*k){
            if(!counters[i])
                available.insert(i);
        }
        int index = k, cycle_start = -1;
        FOR(i, k, n){
            // pick the smallest element from the heap.
            set<int>::iterator it = available.begin();
            nos[index++] = *it;
            counters[*it]++;
            
            // remove the newly inserted element from heap.
            available.erase(it);
            if(nos[i-k] < 2 * k)
                counters[nos[i-k]]--;
            if(nos[i-k] < 2 * k && counters[nos[i-k]] == 0){
                /* if the element at index (i-k) is not used anywhere else
                in the range (i - k, i) then we insert it again in the heap. */
                available.insert(nos[i-k]);
            }
            
            // Check if there is a loop in the numbers generated.
            if(is_looping(nos, k, index)){
                cycle_start = index - k;
                break;
            }
        }

        if(cycle_start == -1){
            cout << nos[n-1] << endl;
        }
        else{
            cout << nos[ cycle_start + ((n - cycle_start) % (k + 1) - 1)] << endl;
        }
    }
    return 0;
}