Curd Producers

This post is in reference to SPOJ Curd Producers CURDPROD.

You have several machines, each producing one item at its own speed. One might produce every 5 seconds, another every 1000.

The question: what is the minimum time required to produce T items?

curdprod

The first calculation required is: how many items were produced by time X? This is a simple O(machines_num) integer division calculation, as follows:

uint64 production(vector<uint32>& machines, uint64 time) {
	uint64 total = 0;
	for (uint32 m_ix = 0; m_ix < machines.size(); m_ix++) {
		total += time / machines[m_ix];
	}
	return total;
}

Also, in the problem the maximum time is limited to 1000000000000000001. So, we have a bounded search space where the result at a given time is easy to calculate. What we've got here is a binary search.

My solution is in git and below:

Leave a Reply