← 返回题目列表

Codeforces · 775/A

A. 大学时间表

中文机器翻译题面 查看原题

在这个问题中,您的任务是为教授和学生团体制定大学一周的课程表。考虑每周有 6 个教育日,每个教育日的最大班级数为 7(每个教育日的班级数从 1 到 7)。

已知大学里有n名学生学习,m名教授工作,有一间教室上课。此外,您还有一个 n × m 大小的二维数组,其中包含以下信息。第 i 行第 j 列的数字等于 j 教授一周内必须为 i 组授课的课数。您输出的时间表必须满足上述数组的要求。

日程安排还有其他几个条件。一位教授不能主持多于一堂课。同样,单个学生小组不能同时上多于一个班级。

让我们为教授和学生群体定义一个疲劳函数。将此函数称为 f。

单教授疲劳度按以下方式计算。让我们看一下这位教授在第 6 个教学日的每一天必须教授的课程。令 x 为教授在第 i 天首先教授的课程数,令 y — 该教授的最后一堂课。那么值(2 + y - x + 1)·(2 + y - x + 1) 必须添加到教授的疲劳中。如果教授在第 i 天没有课,则不会增加教授的疲劳。

对于单个学生团体的疲劳度计算方法类似。让我们看看该组在 6 个教育日中的每一天的课程。令 x 为该组在第 i 天的第一节课的人数,并令 y — 该组的最后一节课。然后必须将值 (2 + y - x + 1)·(2 + y - x + 1) 添加到该组的疲劳中。如果学生小组在第 i 天没有课,则不会增加小组的疲劳度。

因此,函数 f 的值等于所有 n 个学生组和所有 m 个教授的总{疲劳}。

你的任务是提出这样一个时间表,使函数 f 的值最小化。

评审团准备了这个问题的一些解决方案。对于每次测试,您都会获得一定数量的分数。它等于陪审团解中的函数 f 的值除以程序输出的时间表函数 f 的值(即程序发现的 {fatigue} 函数的值越小,获得的分数越多),再乘以 100。换句话说,如果陪审团解的 f 值等于 p,而您的解等于 q,您将获得 100·p / q 分(注意,分数是实数)。所有测试的分数将加在一起。目标是获得尽可能多的分数。

输入

第一行包含三个整数n、m和a(1≤n、m、a≤60)——小组数、教授数和教室数。

以下 n 行中的每一行都包含从 0 到 24 的 m 个整数 - 第 i 行中的第 j 个数字等于教授 j 必须对第 i 个学生组进行的课程数。

保证每位教授、每个学生组每周上课数不超过24节,并保证每周总课数不超过根据教室数可上的最大课数的75%。对于所有测试,至少有一个时间表满足所有描述的条件。

输出

在第一行打印函数 f 的最小值。

之后打印空行。

然后按组号升序打印每个学生组的时间表。为每个学生组打印 7 行。每行必须包含 6 个数字。设第i行第j列的数字等于x。如果第j天当前组没有班级编号i,则x必须等于0。否则,x 必须等于将与相应学生组进行相应课程的教授人数。

同时进行的班级数量不得超过教室数量a。

用空行分隔各组的日程表描述。

示例

输入 #1

3 3 1
1 0 0
0 1 0
0 0 1

输出 #1

54
1 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
2 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
3 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

输入 #2

3 1 1
1
1
1

输出 #2

52
1 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
1 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
1 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

输入 #3

5 7 10
1 3 6 0 1 2 4
0 3 0 6 5 1 4
3 5 1 2 3 2 4
2 3 1 1 4 1 2
2 4 3 2 4 3 2

输出 #3

1512
0 0 6 0 0 2
0 7 6 3 3 7
3 1 2 3 2 7
3 7 0 0 0 0
5 3 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 4 0 7 6
4 5 7 4 5 5
7 2 4 4 5 5
7 2 0 4 0 0
0 2 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
4 0 7 2 5 7
5 0 2 5 7 1
2 4 1 2 7 1
2 3 0 0 0 0
0 6 0 0 0 0
0 6 0 0 0 0
0 0 0 0 0 0
0 0 0 5 3 5
0 2 4 7 2 6
0 5 7 0 0 0
1 5 1 0 0 0
2 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 5 7 2 3
0 1 3 2 6 3
5 7 6 5 6 4
5 4 2 2 0 0
1 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

注意

在比赛的主要部分(一周)期间,您的解决方案将通过 100 次初步测试进行评判。前 10 个初步测试可通过链接 http://assets.codeforces.com/files/vk/vkcup-2017-wr2-materials-v1.tar.gz 下载。

比赛结束后(即比赛开始一周后),您发送的最后一个解决方案(得分为正)将被选择在扩展的最终测试中启动。