prithivMLmods/Coder-Stat

1 2<script type="text/x-mathjax-config">3  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});4</script>5<script type='text/javascript' src='http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML'></script>6</script>7 8<h2>Problem J:9Exhibition10</h2>11 12<p>13  The city government is planning an exhibition and collecting industrial products. There are $n$ candidates of industrial products for the exhibition, and the city government decided to choose $k$ of them. They want to minimize the total price of the $k$ products. However, other criteria such as their sizes and weights should be also taken into account. To address this issue, the city government decided to use the following strategy: The $i$-th product has three parameters, price, size, and weight, denoted by $x_i$, $y_i$, and $z_i$, respectively. Then, the city government chooses $k$ items $i_1, . . . , i_k$ ($1 \leq i_j \leq n$) that minimizes the evaluation measure14 15  \[16e = (\sum^k_{j=1}x_{ij}) (\sum^k_{j=1}y_{ij}) (\sum^k_{j=1}z_{ij}),17  \]18 19  which incorporates the prices, the sizes, and the weights of products. If there are two or more choices that minimize $e$, the government chooses one of them uniformly at random.20</p>21 22<p>23You are working for the company that makes the product 1. The company has decided to cut the price, reduce the size, and/or reduce the weight of the product so that the city government may choose the product of your company, that is, to make the probability of choosing the product positive. We have three parameters $A$, $B$, and $C$. If we want to reduce the price, size, and weight to $(1 − \alpha)x_1$, $(1 − \beta)y_1$, and $(1 − \gamma)z_1$ ($0 \leq \alpha, \beta, \gamma \leq 1$), respectively, then we have to invest $\alpha A + \beta B + \gamma C$ million yen. We note that the resulting price, size, and weight do not have to be integers. Your task is to compute the minimum investment required to make the city government possibly choose the product of your company. You may assume that employees of all the other companies are too lazy to make such an effort.24  </p>25 26<h3>Input</h3>27 28<p>29  The input consists of a single test case with the following format.<br>30  <br>31  32$n$ $k$ $A$ $B$ $C$<br>33$x_1$ $y_1$ $z_1$<br>34$x_2$ $y_2$ $z_2$<br>35.<br>36.<br>37.<br>38$x_n$ $y_n$ $z_n$<br>39  <br>40  41  The first line contains five integers. The integer $n$ ($1 \leq n \leq 50$) is the number of industrial products, and the integer $k$ ($1 \leq k \leq n$) is the number of products that will be chosen by the city government. The integers $A$, $B$, $C$ ($1 \leq A, B, C \leq 100$) are the parameters that determine the cost of changing the price, the size, and the weight, respectively, of the product 1.42</p>43 44<p>45Each of the following $n$ lines contains three integers, $x_i$, $y_i$, and $z_i$ ($1 \leq x_i, y_i, z_i \leq 100$), which are the price, the size, and the weight, respectively, of the $i$-th product.46</p>47 48 49<h3>Output</h3>50 51<p>52Output the minimum cost (in million yen) in order to make the city government possibly choose the product of your company. The output should not contain an absolute error greater than $10^{−4}$.53</p>54 55 56 57<h3>Sample Input 1</h3>58 59<pre>6 5 1 2 3605 5 5611 5 5622 5 4633 5 3644 5 2655 5 1</pre>66 67<h3>Sample Output 1</h3>68 69<pre>0.631579</pre>70 71<h3>Sample Input 2</h3>72 73<pre>6 1 1 2 37410 20 30751 2 3762 4 6773 6 9784 8 12795 10 15</pre>80 81<h3>Sample Output 2</h3>82 83<pre>0.999000</pre>