DMOPC '20 Contest 6 P6 - Dumping Buckets

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 3.0s
Memory limit: 256M

Problem type

Your friend Terry has N beautiful buckets. Jealous, you ask to "borrow" them. Your friend Terry is skeptical of your intentions, however, and so has decided that you can borrow the buckets only if you can pass his test.

Terry wants to make sure you know enough about the buckets. To prove you know his buckets, you need to determine the capacities of each bucket, each of which is a positive integer not greater than M.

You complain that you could never guess the capacities, and so he allows you 10^5 operations, before he gets bored and goes home. Initially, all his buckets are full of water. You can ask Terry to empty the i-th bucket, you can ask him to fill the i-th bucket, or you can ask him to dump the i-th bucket's contents into the j-th bucket, discarding any overflow. In the last case, Terry will tell you the change in height of the j-th bucket, that is, if the initial height before dumping is B and after is A, Terry will reply with A - B.

Can you determine the capacities of Terrys' buckets?


This is an interactive problem. The first line of input contains N (2 \le N \le 4 \times 10^4) and M (1 \le M \le 10^4).

You will then begin interaction with Terry, using up to 10^5 operations. If you output E i (followed by a \n character), Terry will empty the i-th bucket. If you output F i (followed by a \n character), Terry will fill the i-th bucket. If you output D i j (followed by a \n character) with i \ne j, Terry will dump the contents of the i-th bucket into the j-th bucket, ignoring overflow. He will then respond with the difference in heights.

If you believe you have the correct list of capacities you may output A followed by a space-separated list of N integers (followed by a \n character), representing your guess of the list of capacities in order from the first bucket to the last. You must terminate your program immediately after performing this operation. Note that this operation does not count towards the limit of 10^5 operations.

For all cases, it is guaranteed that all of the correct numbers in the list are integers in the range [1, M]. Also, the bucket capacities are fixed before the interaction begins and will not depend on your operations.

For 40\% of available marks, 2 \le N \le 3 \times 10^4 and 1 \le M \le 5 \times 10^3 will hold.

If at any point your query is malformed or you exceed the number of available queries, your program will receive -1 and the interactor will terminate. Upon receiving -1, your program should terminate to avoid an undefined verdict.

If you attempt an invalid operation (such as invalid output format), you will receive a PresentationError verdict.

If you exceed the available query limit, you query an invalid bucket, or you output an incorrect final array, you will receive a Wrong Answer verdict.

Please note that you may need to flush stdout after each operation, or interaction may halt. In C++, this can be done with fflush(stdout) or cout << flush (depending on whether you use printf or cout). In Java, this can be done with System.out.flush(). In Python, you can use sys.stdout.flush().

Sample Interaction

>>> denotes your output. Do not print this out.

The buckets have capacities [2, 4, 1].

3 10
>>> E 1
>>> E 3
>>> D 2 1
>>> D 1 2
>>> F 1
>>> D 1 3
>>> A 2 4 1

Sample Explanation

After our two empty operations, the water levels are [0, 4, 0]. When we dump the contents of 2 into 1, we get [2, 0, 0]. The first bucket's water level has increased by 2 units.

Then we dump from 1 into 2, getting [0, 2, 0]. Filling bucket 1, we get [2, 2, 0], and after dumping 1 into 3, we get [0, 2, 1].

Finally, we output the correct array.

This interaction would receive an Accepted verdict, since it correctly guessed the list of capacities and did not exceed the limit of 10^5 operations.


There are no comments at the moment.