Skip to content

Instantly share code, notes, and snippets.

@boompig
Created November 15, 2014 06:41
Show Gist options
  • Save boompig/23c7d0b6c7ea6ea7d068 to your computer and use it in GitHub Desktop.
Save boompig/23c7d0b6c7ea6ea7d068 to your computer and use it in GitHub Desktop.
#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