#4401. 「2024.12二级」排课 暂未评定

时间限制:1000 ms 内存限制:256 MiB 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: root

题目描述

排课是个世界难题。

假设每个学期有 N 个教学班的课需要排,每周有 M 个时间段可以上课,全校共有 K 间教室,不同排课组合方案的个数可能会超过整个宇宙的质子数。更为复杂的是,每个学期排课前,学校还会收集每个教学班任课老师不能上课的时间段,还要保证排课不与老师的时间安排起冲突。

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

输入格式

输入在第一行中给出三个正整数:N()为教学班总数;M()为一周内上课时间段的个数;K()为教室总数。数字间以空格分隔。

以下我们就将教学班、时间段、教室分别从 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.。
当两种冲突都发生时,分两行输出,先输出教学班冲突的信息。发生冲突的教学班暂不安排。

样例

样例输入 1

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

样例输出 1

Perfect Arrangement for 5 classes!

样例输入 2

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

样例输出 2

ERROR: Conflict between 2 and 1.
ERROR: Conflict with instructor for 3.
ERROR: Conflict between 5 and 1.
ERROR: Conflict with instructor for 5.