/*
* ComponentCheckingzeil.cpp
*
* Created on: Sep 26, 2012
* Author: zeil
*/
#include
#include
#include
#include
#include
using namespace std;
const int Limit = 100000;
int componentCount[Limit]; // if k==componentCount[i], then there are k components that still need to have i+1 reviewers
struct Component {
int reviewersRequired; // How many reviewers are needed per component?
int numComponents; // How many components need this same number of reviewers?
int pending; // How many components are about to be assigned a reviewer?
Component* next;
Component (int nReviewers, int nComponents, Component* nxt)
: reviewersRequired (nReviewers), numComponents(nComponents), pending(0), next(nxt)
{}
};
Component* head;
void readComponents (istream& in, int n)
{
fill_n (componentCount, Limit, 0);
for (int i = 0; i < n; ++i)
{
string line;
getline(in, line);
int c, numComponents;
istringstream lineIn (line);
lineIn >> numComponents;
if (!(lineIn >> c))
{
c = numComponents; // only one number on the line - revert to the old input format
numComponents = 1;
}
componentCount[c-1] += numComponents;
}
// Now convert this to a sparse list
head = 0;
for (int i = 0; i < Limit; ++i) {
if (componentCount[i] > 0) {
head = new Component(i+1, componentCount[i], head);
}
}
}
/**
* We have marked one or more components as having been assigned reviewers.
* For each such component, decrement the number of reviewers needed and
* shift its count lower in the array
*
*/
void reassessComponents()
{
Component* current = head;
Component* prev = 0;
int carry = 0;
while (current != 0 && (carry > 0 || current->pending > 0))
{
Component* next = current->next;
current->numComponents += carry - current->pending;
carry = current->pending;
current->pending = 0;
if (current->reviewersRequired == 1)
// This was the final assignment to components needing only a single reviewer
carry = 0;
else
{
// Need to make sure that the next node in the linked list has reviewersRequired
// exactly one less than this.
if (carry > 0 && (next == 0 || current->reviewersRequired != next->reviewersRequired + 1))
{
current->next = new Component(current->reviewersRequired - 1, 0, next);
next = current->next;
}
}
// If our adjustments have caused numComponents to go to zero, delete this node
if (current->numComponents == 0)
{
if (prev == 0)
{
delete head;
current = 0;
head = next;
}
else
{
prev->next = next;
delete current;
current = prev;
}
}
prev = current;
current = next;
}
}
/**
* We have numEngineers, each of whom can review e components.
* Assign them to the components requiring the most reviewers.
*/
void assignReviewers (int e, int numEngineers)
{
for (int j = 0; j < numEngineers; ++j)
{
Component* current = head;
int duties = e;
while (current != 0 && duties > 0)
{
if (current->numComponents - current->pending > 0)
{
int change = min(current->numComponents - current->pending, duties);
current->pending += change;
duties -= change;
}
current = current->next;
}
reassessComponents();
}
}
bool processEngineers (istream& in, int m) {
for (int i = 0; i < m; ++i)
{
string line;
getline(in, line);
int e, numEngineers;
istringstream lineIn (line);
lineIn >> numEngineers;
if (!(lineIn >> e))
{
e = numEngineers; // only one number on line - revert to old input format
numEngineers = 1;
}
assignReviewers (e, numEngineers);
}
return (head == 0);
}
void cleanup()
{
Component* current = head;
while (current != 0)
{
Component* next = current->next;
delete current;
current = next;
}
head = 0;
}
void solveDataSet (istream& in, int n, int m)
{
string line;
getline(in, line);
readComponents (in, n);
bool solved = processEngineers (in, m);
cout << ((solved) ? "1" : "0") << endl;
cleanup();
}
void run (istream& in)
{
int m, n;
while (true)
{
in >> n >> m;
if (n > 0 && m > 0)
solveDataSet (in, n, m);
else
break;
}
}
int main (int argc, char** argv)
{
if (argc > 1) {
ifstream in (argv[1]);
run(in);
} else
run (cin);
return 0;
}