3385 - Perfect Packing 3385 - Empaquetamiento Perfecto 3385 - Perfect Packing

Statistics Sub: 20 | AC: 2 | AC%: 10,00 | Score: 4,88
Created by Torneo Argentino de Programación ACM-ICPC 2015 - Fidel I. Schaposnik
Added by fidels (2015-10-12)
Limits
Total Time: 10000 MS | Test Time: 1000 MS |Memory: 256 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

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 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 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.
Una de las etapas más difíciles de automatizar en una línea de producción industrial de galletitas es la del empaquetado. El objetivo es diseñar un aparato capaz de contar un número preciso G de galletitas para colocar en un paquete, y la dificultad reside en que estas pueden tener formas a veces muy distintas, por ejemplo de diversos animales.

En la fábrica de galletitas en la que trabajan el equipo de diseño no ha podido sobreponerse a estas dificultades. Lo mejor que ha conseguido lograr es una máquina de conteo que al ser activada puede seleccionar Ci galletitas con probabilidad Pi, para i = 1, 2, ..., K. Habiendo gastado ya todo el presupuesto destinado a esta tarea, tendrán que buscar la manera de hacer algo útil con esto.

Afortunadamente, se les ocurrió la siguiente idea para llevar a buen puerto el proyecto. Para construir el empaquetador automático utilizarán N máquinas de conteo como la arriba descripta, junto con un programa regulador especial que llevará a cabo el siguiente proceso de manera iterada. Antes de comenzar la primera iteración se activan las N máquinas de conteo, seleccionando cada una cierta cantidad de galletitas. En cada iteración, el programa elige de las N máquinas el subconjunto no vacío S para el que la suma de las galletitas seleccionadas sea lo más cercana posible al valor deseado G (en el sentido de que el valor absoluto de la diferencia entre dicha cantidad y G sea mínimo). De haber más de un subconjunto que cumpla con esta condición, el programa elige como S a cualquiera de ellos con probabilidad uniforme. A continuación, las galletitas seleccionadas por las máquinas de S se retiran de las mismas para ser empaquetadas en un solo paquete. Finalmente, cada una de las máquinas de S se activa nuevamente para seleccionar cierta cantidad de galletitas, mientras que las máquinas que no pertenecen a S permanecen inalteradas (es decir, con la cantidad de galletitas seleccionadas en la iteración anterior). Este proceso se repite hasta obtener la cantidad deseada M de paquetes.

Por ejemplo, supongamos que hay N = 3 máquinas a las que llamamos m[1], m[2] y m[3], pudiendo cada una de ellas seleccionar C[1] = 1 ó C[2] = 2 galletitas con probabilidad P[1] = P[2] = ½. Si se desea producir M = 2 paquetes con G = 5 galletitas por paquete, un posible desarrollo del proceso sería el siguiente. Antes de comenzar, las tres máquinas seleccionan C[2] = 2 galletitas cada una (esto ocurrirá con probabilidad ½ * ½ * ½ = ). En la primera iteración, el programa puede entonces elegir los subconjuntos {m[1], m[2], m[3]}, {m[1], m[2]}, {m[1], m[3]} y {m[2], m[3]}, cada uno con probabilidad ¼ ya que todos ellos tienen una diferencia de una galletita con la cantidad deseada. Si suponemos que se elige el subconjunto S = {m[2], m[3]}, a continuación se empaquetan las cuatro galletitas seleccionadas por las máquinas m[2] y m[3]. Estas máquinas volverán a activarse, por ejemplo obteniendo que m[2] selecciona C[1] = 1 galletita y m[3] selecciona C[2] = 2 galletitas (lo cual ocurrirá con probabilidad ½ * ½ = ¼). En este punto termina la primera iteración, con las galletitas seleccionadas por las tres máquinas m[1], m[2] y m[3] siendo 2, 1 y 2, respectivamente.,En la segunda iteración el programa debe seleccionar necesariamente el subconjunto S = {m[1], m[2], m[3]}, pues éste contiene exactamente cinco galletitas, las cuales pasarán a formar parte de un nuevo paquete. Finalmente, se activan una vez más las tres máquinas y termina el proceso habiéndose producido los M = 2 paquetes deseados. Nótese que la probabilidad neta de que ocurra el proceso aquí descripto es * ¼ * ¼ = 1/128, y que la cantidad media de galletitas por paquete resultó ser en este caso de 4.5 galletitas (porque se produjeron dos paquetes, uno de cuatro y otro de cinco galletitas).

Su jefe no está completamente convencido de que este sistema vaya a funcionar, de modo que les exige una prueba concreta de la idea. Para convencerlo, bastará que calculen la cantidad esperada de galletitas que hay por paquete luego de producir M paquetes consecutivamente, si suponen que las N máquinas del aparato seleccionan siempre cantidades de galletitas según las probabilidades dadas.
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 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 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 specification

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), 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.
La primera línea contiene cuatro enteros N, K, G y M. El valor N representa la cantidad de máquinas de conteo a utilizar (1 <= N <= 4), K representa el número de posibles cantidades de galletitas que dichas máquinas pueden seleccionar (1 <= K <= 6), G representa la cantidad deseada de galletitas por paquete (1 <= G <= 100), y M representa la cantidad total de paquetes a producir (1 <= M <= 10^7). Cada una de las siguientes K líneas contiene un entero C[i] y un racional P[i], indicando que la máquina de conteo seleccionará C[i] galletitas con probabilidad P[i] (1 <= C[i] <= 100 y 0 < P_i <= 1 for i = 1, 2, ..., K, siendo dado P[i] con exactamente dos dígitos después del punto decimal). Nótese que C[i] ≠ C[j] para i ≠ j, y que además ∑ P[i] = 1.
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), 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 specification

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.
Imprimir en la salida una línea conteniendo un racional que representa la cantidad esperada de galletitas por paquete habiendo producido M paquetes como se describe en el enunciado. Imprimir el resultado con exactamente 6 dígitos luego del punto decimal, redondeando de ser necesario.
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), 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.

Sample input

3 2 5 1
1 0.50
2 0.50

Sample output

4.312500

Hint(s)

Sample input #2
3 2 5 2
1 0.50
2 0.50

Sample output #2
4.327148
Sample input #2
3 2 5 2
1 0.50
2 0.50

Sample output #2
4.327148
Sample input #2
3 2 5 2
1 0.50
2 0.50

Sample output #2
4.327148

Recommendation

We have carefully selected several similar problems: 2156 | 2824 | 1946 | 1811 | 2141 | 1650