TAP2015E - Perfect packing

no tags 

[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/wp-content/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 Ci cookies with probability Pi 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 non-empty 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 m1, m2 and m3, having each of them the possibility to select C1 = 1 or C2 = 2 cookies with probability P1 = P2 = ½. 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 C2 = 2 cookies each (this will happen with probability ½ * ½ * ½ = ⅛). In the first iteration, the software can then choose among the subsets {m1, m2, m3}, {m1, m2}, {m1, m3} and {m2, m3}, each with probability ¼ because they all have a difference of one cookie with the desired number G = 5. Supposing that the subset S = {m2, m3} is chosen, then the four cookies selected by machines m2 and m3 will be packed together. These machines will then be activated again, resulting for example in m2 selecting C1 = 1 cookie and m3 selecting C2 = 2 cookies (which will occur with probability ½ * ½ = ¼). At this point the first iteration ends, the counting machines m1, m2 and m3 having selected 2, 1 and 2 cookies respectively. In the second iteration, the software must necessarily choose the subset S = {m1, m2, m3} 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.



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 ≤ 107). Each of the following K lines contains an integer Ci and a rational Pi, indicating that the counting machines will select Ci cookies with probability Pi (1 ≤ Ci ≤ 100 and 0 < Pi ≤ 1 for i = 1, 2, ..., K, being Pi given with exactly two digits after the decimal marker). Note that Ci ≠ Cfor i ≠ j and that ∑ Pi = 1.



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.



3 2 5 1
1 0.50
2 0.50
3 2 5 2
1 0.50
2 0.50


hide comments
Alex Anderson: 2015-11-04 07:27:13

Looks like 100M double multiplication in worst case is still too slow.

Question for problem setter, if they look: How much slower is my sol'n than the judge? (i.e., would it pass if it had been written in C++ or something?)

Final edit: Cache locality is important!

Last edit: 2015-11-05 08:38:20

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