编程介的小学生 2017-08-31 12:13 采纳率: 20.5%
浏览 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
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题