University Schedule

题意翻译

在这个问题中你会看到一张大学课程表（包括教授和学生组）。一周有 $6$ 天会上课，每天最多上 $7$ 节课（一天中的每一节课从 $1$ 到 $7$ 标号）。 已知此大学内有 $n$ 名学生，$m$ 名教授，$a$ 个教室。你会得到一份二维的表格（$n \times m$ 大小），内容布置如下：第 $i$ 行第 $j$ 列的数值就是第 $j$ 号教授在一周内要给第 $i$ 个学生组上的课的数量。 你所输出的课程表必须要满足上述安排要求。 这里还有一些其他课程表应满足的条件：同一个教授同一时间只能上 $1$ 节课，相似的，同一个学生组同一时间也只能听 $1$ 节课。 现定义一个疲劳函数 $f$（fatigue function）（适用于教授和学生组）。 对于一个教授来说，他的疲劳函数应通过如下方式计算：在 $6$ 天当中的第 $i$ 天，$x$ 代表那天教授上的第一节课的标号，$y$ 代表他上的最后一节课的标号，则那一天教授的疲劳函数增加了 $(2+y-x+1) \times (2+y-x+1)$。 当然如果那天教授没有课，他的疲劳函数不会变化。 相似的，对于一个学生组来说，他们的疲劳函数应通过如下方式计算：在 $6$ 天当中的第 $i$ 天，$x$ 代表那天学生组听的第一节课的标号，$y$ 代表他们听的最后一节课的标号，则那一天他们的疲劳函数增加了 $(2+y-x+1) \times (2+y-x+1)$。 当然如果那天学生组没有课，他们的疲劳函数不会变化。 所以，$f$ 就等于 $n$ 个学生与 $m$ 个教授各自的疲劳函数之和。 你的任务就是安排一张课程表，使得 $f$ 的值最小。 评判安排好了这道题的一些答案。对于每一个测试点你会得到一定的分数，等同于评判给出的 $f$ 值与你求出的 $f$ 值之商乘 $100$。举例：评判给出的 $f$ 为 $p$ 而你给出的 $f$ 为 $q$,则你得到的分数为 $100 \times \frac{p}{q} $（注意：$p,q$ 均为真实的数字）。 此分数会加到你的总分中，你的目标就是尽可能拿到多的分数。 ## 输入格式： 第一行为三个正整数 $n,m,a$（$1 \le n,m,a\le60$），含义已在上文表述。 接下来 $n$ 行每行包含 $m$ 个由 $0$ 至 $24$ 的正整数，第 $i$ 行的第 $j$ 个数代表一周之内第 $j$ 个教授必须要给第 $i$ 个学生组上的课数。 保证每一个教授和学生组一周要上的课不超过 $24$ 节，以及总课数不会多于用 $a$ 个教室在一周之内能上的课的最多数量的 $75\%$（译注：即你可以认为每一节课都可以上到）。每一个输入都满足以上特征。 ## 输出格式： 第一行输出疲劳函数 $f$ 的最小值。 接下来是一个空行。 接下来根据组号从小到大输出课程表。对于每一组输出 $7$ 行，每行 $6$ 个数据。令第 $i$ 行 $j$ 列的数据为 $x$。如果这一组第 $j$ 天没有第 $i$ 节课， $x$ 必须为 $0$。否则 $x$ 就为要上这节课的教授编号。 同时进行的课总数必须严格控制在 $a$ 以内。 用空行分割两个课程表。

题目描述

In this problem your task is to come up with a week schedule of classes in university for professors and student groups. Consider that there are $ 6 $ educational days in week and maximum number of classes per educational day is $ 7 $ (classes numerated from $ 1 $ to $ 7 $ for each educational day). It is known that in university $ n $ students study, $ m $ professors work and there are $ a $ classrooms for conducting classes. Also you have two-dimensional array with $ n×m $ size which contains the following information. The number which stays in $ i $ -th row and $ j $ -th column equals to the number of classes which professor $ j $ must conduct with the group $ i $ in a single week. The schedule which you output must satisfy to array described above. There are several other conditions for schedule. Single professor can not conduct more than one class. Similarly, single student group can not be on more than one class at the same time. Let define a fatigue function for professors and student groups. Call this function $ f $ . To single professor fatigue calculated in the following way. Let look on classes which this professor must conduct in each of the $ 6 $ -th educational days. Let $ x $ be the number of class which professor will firstly conduct in day $ i $ and let $ y $ — the last class for this professor. Then the value $ (2+y-x+1)·(2+y-x+1) $ must be added to professor's fatigue. If professor has no classes in day $ i $ , nothing is added to professor's fatigue. For single student group fatigue is calculated similarly. Lets look at classes of this group in each of the $ 6 $ educational days. Let $ x $ be the number of first class for this group on day $ i $ and let $ y $ — the last class for this group. Then the value $ (2+y-x+1)·(2+y-x+1) $ must be added to this group's fatigue. If student group has no classes in day $ i $ , nothing is added to group's fatigue. So the value of function $ f $ equals to total {fatigue} for all $ n $ student groups and for all $ m $ professors. Your task is to come up with such a schedule which minimizes the value of function $ f $ . Jury prepared some solution of this problem. For each test you will get a certain number of points. It equals to result of division of the value of function $ f $ from the jury solution by the value of function $ f $ for schedule which your program output (i. e. the smaller value of {fatigue} function your program find the more points you will get), multiplied by $ 100 $ . In the other words if the value of $ f $ for jury solution equals to $ p $ and for your solution — to $ q $ , you will get $ 100·p/q $ points (note, that the number of points is a real number). The points will be added together for all tests. The goal is to score as many points as possible.

输入输出格式

输入格式

The first line contains three integers $ n $ , $ m $ and $ a $ ( $ 1<=n,m,a<=60 $ ) — the number of groups, the number of professors and the number of classrooms. Each of the following $ n $ lines contains $ m $ integers from $ 0 $ to $ 24 $ — $ j $ -th number in $ i $ -th line equals to the number of classes with the professor $ j $ must conduct with the $ i $ -th student group. It is guaranteed that the number of classes in week for each professor and for each student group does not exceed $ 24 $ . Also guaranteed that the total number of classes in week does not exceed $ 75 $ % from a maximum number of classes which can be conducted based on the number of classrooms. For all tests there is at least one schedule satisfying all described conditions.

输出格式

In the first line print the minimized value of function $ f $ . After that print blank line. After that print the schedule for each student group in increasing order of group number. For each student group print $ 7 $ lines. Each line must contains $ 6 $ numbers. Let the number at $ i $ -th line and $ j $ -th column equals to $ x $ . If in $ j $ -th day current group has no class number $ i $ , $ x $ must be equals to zero. Otherwise $ x $ must be equals to the number of professor who will conduct the corresponding class with the corresponding student group. The number of classes which will be conducted simultaneously must not exceeds the number of classrooms $ a $ . Separate the description of the schedules for groups with a blank line.

输入输出样例

输入样例 #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 

说明

During the main part of the competition (one week) you solution will be judged on $ 100 $ preliminary tests. The first $ 10 $ preliminary tests are available for download by a link <http://assets.codeforces.com/files/vk/vkcup-2017-wr2-materials-v1.tar.gz>. After the end of the contest (i.e., a week after its start) the last solution you sent (having positive score) will be chosen to be launched on the extended final tests.