在这个问题中,您的任务是为教授和学生团体制定大学一周的课程表。考虑每周有 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 下载。
比赛结束后(即比赛开始一周后),您发送的最后一个解决方案(得分为正)将被选择在扩展的最终测试中启动。