
ZOJ Problem Set  3569
These days MM is interested in the final stage of Plants vs Zombies, called "Dr. Zomboss's revenge". In this stage, MM is provided with an empty map with n rows and m columns as well as n*m plants. MM is required to fill the map with these n*m plants, which come from t different kinds. However, the terrible fact is that, Dr. Zomboss will randomly throw a fire ball to squash MM's precious plants. A fire ball will be randomly placed on any row, squashing an entire row of plants. For instance, for a map with 5 rows and 4 columns, the possibility of squashing the first row is 1/5. MM has been accustomed to the inevitable squashing. What he cannot bear is that many plants of the same kind might be squashed at the same time. For each kind of plants, namely the ith (1 ≤ i ≤ t) kind, if the number of plants squashed is less or equal than b_{i}, called the bearing factor, MM won't care. However, for every additional plant (compared to b_{i}) with the ith kind squashed, MM will get his angry value increased by a_{i}, called argry factor. Now, MM needs to find a way to place his plants which can minimize the expectation of this total angry value and he asked you to tell him what the minimum expectation is. Notice that the initial angry value of MM is 0. Input
There are multiple cases. The first line of each case contains three integers n (1 ≤ n ≤ 10), m (1 ≤ m ≤ 10), t (1 ≤ t ≤ 30), as described above. Output For each test case, output the minimium mathmetical expectation in a single line, rounded to 3 digits after the decimal point.
Sample Input 2 3 2 3 1 1 3 2 2 Sample Output 0.500 Hint we put plants like 1 2 1 2 1 2 If a fire ball is thrown in the first row, the angry value = 1 If a fire ball is thrown in the second row, the angry value = 0 Hence the expactation is 0.5 Author: WAN, Xinyi Contest: ZOJ Monthly, December 2011 