Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

An interesting problem

Revision en2, by farmersrice, 2019-06-03 06:35:53

You have $$$N$$$ cups, each containing some amount of water. Each cup is identical and has maximum capacity $$$M$$$ milliliters. In one operation, you may select any two cups $$$a$$$ and $$$b$$$, which represents pouring water from cup $$$a$$$ to cup $$$b$$$. If the sum of the cups' volume is less than or equal to $$$M$$$, cup $$$a$$$ ends up empty and cup $$$b$$$ contains all the volume of the cups. If the sum of the cups' volume is greater than $$$M$$$, then cup $$$b$$$ ends up filled to capacity $$$M$$$ and cup $$$a$$$ contains the remainder of the water. Suppose the total volume of water in all cups is $$$V$$$. The question is: What is the minimum number of operations necessary to create $$$\left \lfloor{\frac{V}{M}}\right \rfloor$$$ cups of water that are filled to maximum capacity?

No constraints, the problem is original and comes from a real life scenario. My hypothesis is that as long as you merge small to large then it will take the same number of operations, which is also optimal — but I can't think of how to prove this. Any ideas?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English farmersrice 2019-06-03 06:35:53 227
en1 English farmersrice 2019-06-03 06:34:06 835 Initial revision (published)