No Expectations!

To know about expected value, you can read this.

Subtask 1:
At first, let’s sort the array of the mugs’ capacities non-decreasingly. Now, if we give the $i^{th}$ mug to a customer, for the future customers, we can only use the valid mugs in $[i+1, n]$ range. The probability of choosing a mug $i$ for the $1^{st}$ customer is obviously $\frac{1}{n}$. Now, let’s say the jug’s present water amount is $c$ liters and we’ve chosen to give the $i^{th}$ mug to a customer. So, the expected number of times you can serve the customers from this state to the final states is:

$E(i,c) = 1 + \frac{1}{(r-l+1)} \times (E(l, c-a_i) + E(l+1, c-a_i) + … + E(r, c-a_i))$,

where $i< l\leq r$, $l$ is the leftmost index such that $a_i < a_l\leq c-a_i$ and $r$ is the rightmost index such that $a_i < a_r \leq c-a_i$. If $E(i,c)$ is the final state, $E(i,c) = 1$.

From the above relation, we can easily build a dynamic programming solution.
Author’s solution for subtask 1: https://ideone.com/9eZgDh
Complexity: $O(n^2 \times c)$

Subtask 2:
For subtask 2, we just need to optimize the idea of subtask 1. From the relation above, we can see that from a state $E(i,c)$, we can go to the next states only with a fixed water amount of $c-a_i$ liters. If we know the sum of the expected values and the count of the next valid states with $c-a_i$ liters water, we can easily calculate $E(i, c)$. Let, $cnt_k$ is our desired count and $sum_k$ is our desired sum of the expected values with $k$ liters water. Then we can write,

$E(i,c) = 1 + \frac{1}{cnt_{c-a_i}} \times sum_{c-a_i}$

$cnt_k$ and $sum_k$ can be calculated by iterating from the $n^{th}$ index to the $1^{st}$ index. We need to process the mugs with the same capacities together so that the mugs with the same capacities won’t be considered as the next states. See the author’s solution for better understandings.

Author’s solution: https://ideone.com/Nog7Jm
Complexity: $O(n\times c)$