#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; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment