CONTEST  Fixed Partition Contest Management
A technique used in early programming contest strategies involved partitioning the available intellectual capacity of a team into a number of members with each member having a fixed amount of intelligence, different members potentially having different amounts. The sum of the brightness of all members equals the total intellectual capacity of the team.
Given a set of problems, it was the task of the team to assign the problems to different team members, so that they could be solved concurrently. This was made difficult due to the fact that the solution time of a problem might depend on the amount of intelligence available to it. Every problem has a minimum intelligence requirement, but if assigned to a brighter member its solution time might increase or decrease.
In this task, you have to determine optimal assignments of problems to team members. Your program is given the intellectual capacities of the team members available for the solution of problems, and for each problem a description of how its solution time depends on the amount of intelligence available to it. Your program has to find the solution schedule of the problems that minimizes the average solution time for the problems. A solution schedule is an assignment of problems to team members and times, such that no two problems use the same member at the same time, and no problem is assigned to a team member with less brightness than its minimum requirement. The solution time of the problem is the difference between the time when the problem was submitted to be solved (which is the start of the contest at time zero for all problems in this task), and the time that the problem is solved.
Input Specification
The input data will contain multiple test cases. Each test case begins with a line containing a pair of integers m
and n
. The number m
specifies the number of team members (1 <= m <= 3
), and n
specifies the number of problems to be solved (1 <= n <= 10
).
The next line contains m
positive integers giving the intelligence amounts of the m
team members. Following this are n
lines, describing the timebrightness tradeoffs for each of the n
problems. Each line starts with a positive integer k
(k <= 10
), followed by k
pairs of positive integers s_{1},t_{1},s_{2},t_{2},...,s_{k},t_{k}
that satisfy s_{i} < s_{i+1}
for 1 <= i < k
. The minimum intelligence requirement of the problem is s_{1}
, i.e. it cannot be solved by a member with less intellectual capacity than this number. If the problem is solved by a team member with brightness s
, where s_{i} <= s < s_{i+1}
for some i
, then its solution time will be t_{i}
. Finally, if the problem is solved by a team member with intellectual capacity s_{k}
or more, then its execution time will be t_{k}
.
A pair of zeroes will follow the input for the last test case.
You may assume that each problem will be solved in exactly the time specified for the given brightness, regardless of the number of other problems being solved by other team members at the same time. No problem will have an intelligence requirement larger than that of the brightest team member.
Output Specification
For each test case, first display the case number (starting with 1
and increasing sequentially). Then print the minimum average solution time for the set of problems with two digits to the right of the decimal point. Follow this by the description of a solution schedule that achieves this average solution time. Display one line for each problem, in the order they were given in the input, that identifies the problem number, the member used to solve it (numbered in the order given in the input), the time when the member started to solve the problem, and the time when the problem was solved. Follow the format shown in the sample output, and print a blank line after each test case.
Sample Input
2 4 40 60 1 35 4 1 20 3 1 40 10 1 60 7 3 5 10 20 30 2 10 50 12 30 2 10 100 20 25 1 25 19 1 19 41 2 10 18 30 42 0 0
Sample Output
Case 1 Average solution time = 7.75 Problem 1 is solved by member 2 from 0 to 4 Problem 2 is solved by member 1 from 0 to 3 Problem 3 is solved by member 1 from 3 to 13 Problem 4 is solved by member 2 from 4 to 11 Case 2 Average solution time = 35.40 Problem 1 is solved by member 3 from 19 to 49 Problem 2 is solved by member 2 from 0 to 25 Problem 3 is solved by member 3 from 0 to 19 Problem 4 is solved by member 2 from 25 to 66 Problem 5 is solved by member 1 from 0 to 18
hide comments
:D:
20141208 14:58:20
On side note: this problem could require a precise printing of values that can't be properly stored in float variables. For example in printf 0.015 will be aproximated to 0.01, where the correct rounding would be 0.02. I don't know if the judge ignores those small issues. If not, you should add some small value on printing (I used 0.0001) 

:D:
20141208 14:58:20
I'm not sure about that. I also had differences in sheldue but got AC. I see 3 posiblilites here:


Shaka Shadows:
20141208 14:58:20
Have the problem setter noticed that the problem may have multiple solutions? I have checked my output with the official test data and the only difference is the schedule I print, which is also valid. Last edit: 20101013 20:53:28 
Added by:  Wanderley GuimarÄƒes 
Date:  20070921 
Time limit:  0.200s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  University of Ulm Local Contest 2003 