TAP2015E  Perfect packing
[Due to SPOJ restrictions, this problem has been modified with respect to the original version used in the Argentinian Programming Tournament of 2015 in order to have multiple test cases per input file. The original version of this problem (in Spanish) can be found at http://torneoprogramacion.com.ar/wpcontent/uploads/2015/09/pruebaTAP2015.pdf ]
One of the most difficult stages to automate in an industrial cookie production line is the one corresponding to packing. The goal is to design an apparatus capable of counting a precise number G of cookies to be put in a package, and the challenge resides in the fact that the cookies may have markedly different shapes, e.g. of various animals.
In the cookie factory where you work the design team has been unable to overcome these difficulties. The best design they have achieved corresponds to a counting machine which, when activated, can select C_{i} cookies with probability P_{i} for i = 1, 2, ..., K. Having already spent the entire budget allocated to this task, you will have to find a way to make something useful out of this.
Fortunately, you have come up with the following idea to save the project. You shall build an automated packager using N counting machines such as the one described above, along with a special regulating software that will perform the following process iteratively. Before starting the first iteration the N counting machines are activated, each one selecting certain number of cookies. In each iteration, the software will choose a nonempty subset S of the N machines such that the sum of the selected cookies is as close as possible to the desired value G (in the sense that the absolute value of the difference between this number and G is minimum). If there is more than one subset satisfying this condition, the software will choose as S any of them with uniform probability. The cookies selected by the counting machines in S will then be removed and packed together. Finally, each of the machines in S will be activated again in order for it to select certain number of cookies, while the counting machines not in S remain unaltered (that is, with the number of cookies they selected in the previous iteration). This process will be repeated until the desired number M of packages has been obtained.
For example, let's assume there are N = 3 counting machines, which we will call m_{1}, m_{2} and m_{3}, having each of them the possibility to select C_{1} = 1 or C_{2} = 2 cookies with probability P_{1} = P_{2} = ½. If we want to produce M = 2 packages with G = 5 cookies per package, a possible turn of events is the following. Before starting, the three machines select C_{2} = 2 cookies each (this will happen with probability ½ * ½ * ½ = ⅛). In the first iteration, the software can then choose among the subsets {m_{1}, m_{2}, m_{3}}, {m_{1}, m_{2}}, {m_{1}, m_{3}} and {m_{2}, m_{3}}, each with probability ¼ because they all have a difference of one cookie with the desired number G = 5. Supposing that the subset S = {m_{2}, m_{3}} is chosen, then the four cookies selected by machines m_{2} and m_{3} will be packed together. These machines will then be activated again, resulting for example in m_{2} selecting C_{1} = 1 cookie and m_{3} selecting C_{2} = 2 cookies (which will occur with probability ½ * ½ = ¼). At this point the first iteration ends, the counting machines m_{1}, m_{2} and m_{3} having selected 2, 1 and 2 cookies respectively. In the second iteration, the software must necessarily choose the subset S = {m_{1}, m_{2}, m_{3}} as it contains exactly five cookies, which will therefore be packed together. Finally, the three counting machines will be activated once more and the process will end, having produced the M = 2 desired packages. Note that the net probability for the process here described is ⅛ * ¼ * ¼ = 1/128, and that the average number of cookies per package is in this case 4.5 (because two packages were produced, one of them having four and the other five cookies).
Your boss is not completely convinced that this system will work, so he requires from you some concrete proof of concept. To convince him, it will suffice to calculate the expected number of cookies per package after producing M packages consecutively, if you assume that the N counting machines always select cookies according to the given probabilities.
Input
There are multiple test cases in the input file. For each test case, the first line contains four integers N, K, G and M. The value N represents the number of counting machines to use (1 ≤ N ≤ 4), K represents the number of possible quantities of cookies each counting machine can select (1 ≤ K ≤ 6), G represents the desired number of cookies per package (1 ≤ G ≤ 100), and M represents the total number of packages to produce (1 ≤ M ≤ 10^{7}). Each of the following K lines contains an integer C_{i} and a rational P_{i}, indicating that the counting machines will select C_{i} cookies with probability P_{i} (1 ≤ C_{i} ≤ 100 and 0 < P_{i} ≤ 1 for i = 1, 2, ..., K, being P_{i} given with exactly two digits after the decimal marker). Note that C_{i} ≠ C_{j }for i ≠ j and that ∑ P_{i} = 1.
Output
For each test case, print one line containing a rational representing the expected number of cookies per package after having produced M packages as described in the problem statement. Print the result with exactly 6 digits after the decimal marker, rounding if necessary.
Example
Input: 3 2 5 1 1 0.50 2 0.50 3 2 5 2 1 0.50 2 0.50 Output: 4.312500 4.327148
hide comments
Alex Anderson:
20151104 07:27:13
Looks like 100M double multiplication in worst case is still too slow.

Added by:  Fidel Schaposnik 
Date:  20151028 
Time limit:  4s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU JSMONKEY 
Resource:  Argentinian Programming Tournament 2015 