Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Projects
Description In a certain week, a company wants to finish For each project the company knows from experience the probability that the project will be completed within a week, as a function of the number of employees working on it. These probabilities are given as percentages i (with 1 ≤ i ≤ m) is the number of the project and j is the number of people working on it. Of course, when nobody is working on a project i, the probability p_{i}_{0} is zero percent.If project Of course the company wants to maximise its total expected profit
Input The first line of the input file contains a single number: the number of test cases to follow. Each test case has the following format: - One line with one integer
*m*with 1 ≤*m*≤ 100: the number of projects. - One line with one integer
*n*with 0 ≤*n*≤ 100: the maximal number of available employees. - One line with one integer salary with 0 ≤
`salary`≤ 1,000: the salary of one employee. Remember that the salary is given in euros. *m*lines, each line corresponding to a project*i*, containing*n*integers*p*_{i}_{1},*p*_{i}_{2}, …,*p*(the percentages, with 0 ≤_{in}*p*_{i}_{1},*p*_{i}_{2}, …,*p*≤ 100), followed by two integers corresponding to the_{in}`reward`and the`punishment`for project*i*. All values are separated by single spaces. Both`reward`and`punishment`are given in euros and are between 0 and 100,000 (boundaries included).
Output For every test case in the input file, the output should contain two lines. - The first line contains the maximal expected profit in eurocents.
- The second line contains the total number of external employees that must be hired in order to achieve this maximal expected profit. If the maximal expected profit can be achieved by different (total) numbers of employees, then these different numbers must be given in increasing order. Numbers have to be separated by single spaces.
Sample Input 3 1 4 200 90 100 100 100 2000 0 2 2 100 80 80 2100 500 0 100 1700 500 3 4 100 100 80 80 70 1000 100 100 90 80 90 500 50 100 70 60 50 700 100 Sample Output 162000 1 100000 1 2 190000 3 Source |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator