编程介的小学生 2017-08-31 12:13 采纳率: 0.2%
浏览 678
已采纳

Classroom Scheduling

It's somewhat natural, at the start of each semester, that we go to some classroom to have a lesson unwillingly, only to find it filled up with students from another class. I wonder how they are arranging the resources. So that's why I'm currently engaged in a classroom scheduling project.

Time being extremely tight, I have to focus on the overall system behaviors, leaving the core, but difficult part unfinished. That's the classroom auto-arrangement engine. But I'm not worried, because I can ask for help here.

Let's consider an easier scenario first.

We have many classroom buildings, each belonging to a specific academy. Every classroom inside is associated with its capacity. Now, at the start of a semester, we got a lot of course requests by each academy to be scheduled simultaneously in these classrooms. Certainly, a course can only be scheduled to a classroom where the number of attending students is no greater than the classroom's capacity. Note that these courses should be held simultaneously without resource conflicts, situations such as holding course A on Monday and course B on Tuesday should not be considered.

The best scheduling plan is defined as follows:

  1. The plan must meet a maximum count of course requests.

  2. The count of courses not arranged in the building their academy possesses should be minimized, provided that condition 1 is met. This eases the management and saves a lot of campus-wide commuting.

Input

There are multiple test cases.

The first line of ease test case contains the number A of academies in the university. A line with A = 0 ends the input data, and this should not be processed.

Next, there are A lines describing each academy, with an integer C, the count of classrooms in the building the academy possesses, followed by C integers not more than 200, stating the capacity of each classroom. The identifier for each academy starts at one.

Note that the overall number of classrooms in the university is at most 100.

This is followed by R (0 < R <= 100), the count of course requests, and hence R lines describing each request in the format Ai Si, where Ai stands for the academy submitting the course request and Si being the total number of students attending the course.

Output

For each test case, you should produce one line of output, consisting of two numbers separated by exactly one space: the maximum count of course requests met, and the minimum count of course not arranged in the building their academy possesses, out of the total arranged courses.

Sample Input

2
3 100 100 100
3 50 50 50
7
1 50
1 50
1 100
2 50
2 50
2 100
2 200
0

Sample Output

6 2

  • 写回答

1条回答 默认 最新

  • threenewbee 2017-09-15 15:46
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥20 如何通过代码传输视频到亚马逊平台
  • ¥15 php查询mysql数据库并显示至下拉列表中
  • ¥15 freertos下使用外部中断失效
  • ¥15 输入的char字符转为int类型,不是对应的ascall码,如何才能使之转换为对应ascall码?或者使输入的char字符可以正常与其他字符比较?
  • ¥15 devserver配置完 启动服务 无法访问static上的资源
  • ¥15 解决websocket跟c#客户端通信
  • ¥30 Python调用dll文件输出Nan重置dll状态
  • ¥15 浮动div的高度控制问题。
  • ¥66 换电脑后应用程序报错
  • ¥50 array数据同步问题