// Problem idea by Albert Lai // Problem written by Albert Lai // This solution written by Thomas Tang #include #include #include #include using namespace std; typedef struct { int time; int amount; } Event; int gcd(int a, int b) { int tmp; if (a < b) { tmp = a; a = b; b = tmp; } while (b > 0) { int rem = a % b; a = b; b = rem; } return a; } int lcm(int a, int b) { int g = gcd(a, b); return a/g*b; } main() { int rateG, rateL; int scale; int numDish, numCall; int i, j; int currentTime; list lepEvent; Event ev; scanf("%d%d%d%d", &rateG, &rateL, &numDish, &numCall); // scale the rates by LCM to avoid using floating point numbers, which // could cause numerical instability (try test input 6 without it) scale = lcm(rateG, rateL); currentTime = 0; for (i = 0; i < numDish; i++) { int s, g; scanf("%d%d", &s, &g); s *= scale; g *= scale; currentTime += g/rateG; ev.time = currentTime; ev.amount = s - g; lepEvent.push_back(ev); } // add events whenever Leporello finishes list::iterator li, next; for (li = lepEvent.begin(); li != lepEvent.end(); ) { if (li->amount == 0) { li++; continue; } int timeFinish = li->time + li->amount/rateL; next = li; next++; if (next != lepEvent.end()) { // there is next if (next->time > timeFinish) { // will finish before next ev.time = timeFinish; ev.amount = 0; lepEvent.insert(next, ev); li++; } else { // won't finish before next, merge with next li->amount += next->amount; lepEvent.erase(next); } } else { // last one ev.time = timeFinish; ev.amount = 0; lepEvent.push_back(ev); break; } } bool clear = true; int timeSince = -1; li = lepEvent.begin(); int timeNext; if (lepEvent.size() > 0) { timeNext = li->time; } else { timeNext = INT_MAX; } for (i = 0; i < numCall; i++) { int ctime; scanf("%d", &ctime); ctime *= scale; while (!(timeSince < ctime && ctime < timeNext && clear) && !(timeSince <= ctime && ctime <= timeNext && !clear)) { li++; timeSince = timeNext; if (li == lepEvent.end()) { // no more event clear = true; timeNext = INT_MAX; break; } timeNext = li->time; clear = !clear; } if (clear) { printf("clear\n"); } else { printf("full\n"); } } }