荔园在线

荔园之美,在春之萌芽,在夏之绽放,在秋之收获,在冬之沉淀

[回到开始] [上一篇][下一篇]


发信人: huhaiming (一生只爱她), 信区: Program
标  题: problem E
发信站: 荔园晨风BBS站 (Sat May 24 20:06:23 2003), 站内信件


Classroom Scheduling


Time limit: 1 Seconds   Memory limit: 32768K
Total Submit: 0   Accepted Submit: 0

------------------------------------------------------------------------
--------

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


Author: ccmouse



------------------------------------------------------------------------
--------

Submit   Back   Status

--

菩提本无树,明镜亦非台

本来无一物,何处惹尘埃

※ 来源:·荔园晨风BBS站 bbs.szu.edu.cn·[FROM: 192.168.0.200]


[回到开始] [上一篇][下一篇]

荔园在线首页 友情链接:深圳大学 深大招生 荔园晨风BBS S-Term软件 网络书店