本题没有可用的提交语言。

问题描述

早期编程竞赛策略中采用的一种技术是将团队的可用智力容量划分为若干成员，每个成员拥有固定的智力值，不同成员的智力值可能不同。所有成员的智力值之和等于团队的总智力容量。

给定一组问题，团队的任务是将这些问题分配给不同的成员，以便可以并发解决。由于问题的解决时间可能取决于分配给它的智力值，这使得任务变得复杂。每个问题都有一个最低智力要求，但如果分配给智力更高的成员，其解决时间可能会增加或减少。

在此任务中，你需要确定问题到团队成员的最优分配方案。你的程序将获得可用于解决问题的团队成员的智力值，以及每个问题的解决时间如何依赖于可用智力值的描述。你的程序需要找到一个问题解决时间表，使得问题的平均解决时间最小。解决时间表是将问题分配给团队成员和时间，满足以下条件：

1. 没有两个问题在同一时间使用同一成员；
2. 没有问题分配给智力值低于其最低要求的成员。 问题的解决时间是从问题提交解决的时间（本任务中所有问题的提交时间均为比赛开始的0时刻）到问题解决的时间差。

输入格式

输入数据包含多个测试用例。每个测试用例的第一行包含两个整数 $m$ 和 $n$。$m$ 表示团队成员的数量（$1 \leq m \leq 3$），$n$ 表示需要解决的问题数量（$1 \leq n \leq 10$）。

接下来的一行包含 $m$ 个正整数，表示 $m$ 个团队成员的智力值。随后是 $n$ 行，描述每个问题的解决时间与智力值的关系。每行以一个正整数 $k$（$k \leq 10$）开头，后跟 $k$ 对正整数 $s_1,t_1,s_2,t_2,\ldots,s_k,t_k$，满足 $s_i < s_{i+1}$（$1 \leq i < k$）。问题的最低智力要求是 $s_1$，即无法由智力值低于此值的成员解决。如果问题由智力值 $s$ 满足 $s_i \leq s < s_{i+1}$ 的成员解决，则其解决时间为 $t_i$。最后，如果问题由智力值 $s_k$ 或更高的成员解决，则其解决时间为 $t_k$。

最后一个测试用例后跟一对零。

你可以假设每个问题的解决时间完全由给定的智力值决定，不受其他成员同时解决的问题数量的影响。没有问题的智力要求会超过最聪明成员的智力值。

输出格式

对于每个测试用例，首先显示用例编号（从1开始依次递增）。然后打印最小平均解决时间，保留两位小数。接着打印实现该平均解决时间的解决时间表。按输入顺序为每个问题打印一行，包括问题编号、用于解决问题的成员编号（按输入顺序编号）、成员开始解决问题的时间以及问题解决的时间。遵循样例输出中的格式，每个测试用例后打印一个空行。

输入样例 1

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

输出样例 1

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

来源

Ulm Local 2003