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 bi, called the bearing factor, MM won't care. However, for every additional plant (compared to bi) with the ith kind squashed, MM will get his angry value increased by ai, 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.
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. Each of the following t lines contains three integers discribing a kind of plant: the number of plant ci (1 ≤ ci ≤ n*m), the bearing factor bi (1 ≤ bi ≤ ci)and the angry factor ai (1 ≤ ai ≤ 100). We assert that the sum of ci equals to n*m. Process to the end of file.
OutputFor each test case, output the minimium mathmetical expectation in a single line, rounded to 3 digits after the decimal point.
2 3 2 3 1 1 3 2 2
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