sign-games.cpp

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <functional>
#include <set>
#include <stdlib.h>
#include <math.h>
using namespace std;

typedef unsigned long long ull;

int numDigits(ull n) {
    int i = 0;
    if (n == 0) return 1;

    while (n > 0) {
        n = n / 10;
        i++;
    }

    return i;
}

// string is contiguous numbers here
ull processStr(string &s, ull n, int w, set<ull> &numQ) {
    int sLen = s.size();
    int startSegSize = numDigits(n);
    int stopSegSize = min(numDigits(n + w), sLen);
    //cerr << "using segSize " << startSegSize << endl;
    //cerr << "stopping at " << stopSegSize << endl;

    for(int segSize = startSegSize; segSize <= stopSegSize; segSize++) {

        for (int idx = 0; idx <= sLen - segSize; idx++) {
            string subseq = s.substr(idx, segSize);

            // convert subsequence to num
            ull num = 0;
            for (int i = 0; i < segSize; i++) {
                num *= 10;
                num += subseq[i] - '0';
            }
            //cerr << "found num = " << num << endl;

            if (num == n + 1) {
                n++;

                // use numQ to fill up the gaps
                while (! numQ.empty()) {
                    int next = *(numQ.begin());
                    if (next < n + 1) {
                        numQ.erase(next);
                    } else if (next == n + 1) {
                        numQ.erase(next);
                        n++;
                    } else {
                        // too big
                        break;
                    }
                }
            } else if (num > n) {
                // now, add this number to the queue of fun things
                numQ.insert(num);
            }

            // do not add small #s to numQ
        }

        // recalculate when to stop
        stopSegSize = min(numDigits(n + w), sLen);
    }

    return n;
}

/**
 * Extract all numbers from line
 */
ull processLine (string s, ull n, int w, set<ull> &windowQ) {
    // first, split into several lines
    vector<string> sequences;
    size_t sSize = s.size();

    int start = 0;
    int len = 0;

    for (int i = 0; i < sSize; i++) {
        if (s[i] >= '0' && s[i] <= '9') {
            len++;
        } else {
            if (len > 0) {
                sequences.push_back(s.substr(start, len));
            }
            start = i + 1;
            len = 0;
        }
    }
    if (len > 0) {
        sequences.push_back(s.substr(start, len));
    }

    size_t seqLen = sequences.size();
    //cerr << "subsequences: ";
    for (int i = 0; i < seqLen; i++) {
        //cerr << sequences[i] << " ";
    }
    //cerr << endl;

    ull old_n = n - 1;

    while (old_n != n) {
        old_n = n;

        for (int i = 0; i < seqLen; i++) {
            //cerr << "searching for n = " << n << endl;
            n = processStr(sequences[i], n, w, windowQ);
            //cerr << "windowQ.size() = " << windowQ.size() << endl;
            //cerr << "n = " << n << endl;
        }
    }

    return n;
}

int main() {
    // number of test cases
    ull m;

    cin >> m;

    for(int t = 1; t <= m; t++) {
        // number of signs seen
        ull k, w;
        cin >> k >> w;
        ull n = 0;
        //cerr << "w = " << w << endl;

        // skip a line
        string s;
        getline(cin, s);
        set<ull> windowQ;

        for (int i = 0; i < k; i++) {
            getline(cin, s);
            //cerr << "sign " << i << ": " << s << endl;
            n = processLine(s, n, w, windowQ);

            // now cull all elements which are too big
            while (! windowQ.empty()) {
                ull next = *(windowQ.rbegin());
                if (next > n + w) {
                    windowQ.erase(next);
                } else {
                    break;
                }
            }

            //cerr << "windowQ size = " << windowQ.size() << endl;
        }

        // TODO show the other number as well
        cout << "Case " << t << ": " << n;

        if (windowQ.size() > 0) {
            ull last = 0;
            for (set<ull>::iterator it = windowQ.begin(); it != windowQ.end(); it++) {
                if (*it <= n + w) {
                    last = *it;
                } else {
                    break;
                }
            }

            cout << " " << last << endl;
        } else {
            cout << " " << n << endl;
        }

    }
    return 0;
}