240894 - 排课

题目描述

排课是个世界难题。

假设每个学期有 N 个教学班的课需要排,每周有M个时间段可以上课,全校共有K间教室,不同排课组合方案的个数可能会超过整个宇宙的质子数。

更为复杂的是,每个学期排课前,学校还会收集每个教学班任课老师不能上课的时间段,还要保证排课不与老师的时间安排起冲突。

当然,本题不是要求你实现一个排课算法,而是要求你实现一个排课方案检查算法。即给定每个教学班上课的时间和地点,你需要检查这个时间段和地点是否只有这一个班上课,并且这个上课时间不会正好是任课老师不能上课的时间。

输入

输入在第一行中给出三个正整数:

N(≤10^4)为教学班总数;M(≤40)为一周内上课时间段的个数;K(≤10^3)为教室总数。

数字间以空格分隔。以下我们就将教学班、时间段、教室分别从1开始顺序编号。

随后 N行,每行给出一个教学班的任课教师时间限制和排课的信息。

格式如下: L T[1] ... T[L] Time Room

其中L是任课教师的时间限制数量(<M),后面给出L个该老师不能上课的时间段编号;Time 是该教学班安排的上课时间段编号,Room 是上课教室编号。

输出

如果给定的课表安排是完全无冲突的,则在一行内输出:Perfect Arrangement for N classes! 其中N是教学班数量。

如果课表有冲突,则需要输出冲突原因。我们首先假设教学班是按照编号递增序进行排课的,教学资源先到先得。

如果后面安排的教学班 A跟前面的教学班 B 排在了同一个时间和地点,则在-行中输出 ERROR: Conflict between A and B.

如果教学班 A的上课时间跟任课教师有冲突,则在一行中输出ERROR:Conflict with instructor for A.

当两种冲突都发生时分两行输出,先输出教学班冲突的信息。发生冲突的教学班暂不安排。

样例

输入

5 20 10
2 1 5 10 7
0 10 3
5 2 4 6 8 10 3 3
3 10 3 18 15 1
1 20 19 10

输出

Perfect Arrangement for 5 classes!

输入

5 20 10
2 1 5 10 7
0 10 7
5 2 4 6 8 10 6 3
3 10 3 18 6 3
2 20 10 10 7

输出

ERROR:Conflict between 2 and 1.
ERROR:Conflict with instructor for 3.
ERROR:Conflict between 5 and 1.
ERROR:Conflict with instructor for 5.
标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 12
通过人数 7
金币数量 1 枚
难度 入门


上一题 下一题