Subtask 1

Let ~cur(x)~ be the current amount of water in bucket ~x~ and ~cap(x)~ be the maximum amount of water in bucket ~x~.

Note that when we pour bucket ~x~ into bucket ~y~, if the answer ~z~ is less than ~cur(x)~, we know ~cap(y) = cur(y) + z~. Otherwise, we know ~cap(x) = z~.

That's all well and good if we know ~cur(x)~ and ~cur(y)~, but what if we don't?

Well if we take a full bucket, for instance, and pour it into a bucket with known volume, and then fill it and pour again, we have quite a bit of information. To be specific, if we take a bucket with known volume ~cur(x)~ and a full bucket of unknown capacity ~y~, then we can dump ~y~ into ~x~ to start. Call this return value ~a~. Then we fill ~y~ again, and dump from ~y~ into ~x~. We get the return value ~b~. Evidently, ~cur(x) = cur(x) + a + b~.

Now, if ~b = 0~, we know that ~x~ is full, so ~cap(x) = cur(x)~, and we need to determine the bucket ~y~, which is empty.

If ~b = a~, we know that ~cap(y) = a~.

If ~b < a~, we can actually apply both observations, the reasoning of which is left as an exercise to the reader.

We can move left-to-right in our array and consider our ~N - 1~ pairs. After ~3~ operations, we have necessarily found one of our two buckets, and have left the other with a known volume.

In order to start with a bucket of known volume, we empty out bucket ~1~.

After our ~3(N - 1) + 1~ operations, we can take any bucket, and keep filling and dumping it into the remaining bucket we require. We keep doing this while our dump operations return a positive number, and while the current volume is smaller than ~M~, since if it is equal to ~M~, we know the capacity is ~M~.

Operations: ~3N + 2M~

Full Solution

We are quite close to the full solution. Let's split up our pair processing part into two cases. In all cases, we have one bucket of unknown capacity and known volume and a full bucket (also of unknown capacity).

Case 1: the bucket of unknown capacity has zero volume

In this case, other than the very start, we can actually prove that we will always get here with another bucket ~k~ of known volume. A little paper work should reveal this. In this case, we can do the following, assuming ~x~ is the empty bucket.

• dump ~y~ into ~x~
• dump ~k~ into ~x~

If the second operation returns ~0~, we know the capacity of ~x~. Otherwise, we know the capacity of ~y~.

Case 2: the bucket of unknown capacity has positive volume

In this case, we do the following, assuming ~y~ is the full bucket.

• dump ~y~ into ~x~
• dump ~x~ into ~y~

Recall that we know ~cur(x) > 0~. After the first operation, if there was no overflow, we have ~cur(x) > cap(y)~. In such case, the second operation will overflow, and we will know ~cap(y)~.

On the other hand, if the second operation does not overflow, we know that ~cur(x) \le cap(y)~, and thus that ~cap(x) = cur(x)~, so this tells us ~cap(x)~.

Final Thoughts

The main observation here is that after processing a pair, we have a bucket of known volume, and a full bucket. If the bucket we don't know is empty, we have an extra bucket of known volume which is non-empty. Otherwise, if the bucket we don't know is non-empty, we can apply case 2, and reach one of our cases again.

To wrap this up, we can apply the ~2M~ strategy above.

Operations: ~2N + 2M~

P.S.: since a dump operation empties the source bucket, we don't need the empty operation.

P.S.S: We can actually save one operation in the second phase of the problem, since we have a bucket of known volume (alongside our last required bucket). Thanks to wleung_bvg for pointing this out.