{"problem":{"name":"A. University Schedule","description":{"content":"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 classe","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":10000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF775A"},"statements":[{"statement_type":"Markdown","content":"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).\n\nIt 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.\n\nThere 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.\n\nLet define a _fatigue_ function for professors and student groups. Call this function _f_.\n\nTo 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_.\n\nFor 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_.\n\nSo the value of function _f_ equals to total {fatigue} for all _n_ student groups and for all _m_ professors.\n\nYour task is to come up with such a schedule which minimizes the value of function _f_.\n\nJury 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.\n\n## Input\n\nThe 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.\n\nEach 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.\n\nIt 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.\n\n## Output\n\nIn the first line print the minimized value of function _f_.\n\nAfter that print blank line.\n\nAfter 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.\n\nThe number of classes which will be conducted simultaneously must not exceeds the number of classrooms _a_.\n\nSeparate the description of the schedules for groups with a blank line.\n\n[samples]\n\n## Note\n\nDuring 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](//assets.codeforces.com/files/vk/vkcup-2017-wr2-materials-v1.tar.gz).\n\nAfter 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.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"在本题中，你的任务是为大学的教授和学生小组制定一周的课程表。假设一周有 #cf_span[6] 个教学日，每个教学日最多有 #cf_span[7] 节课（每个教学日的课程编号从 #cf_span[1] 到 #cf_span[7]）。\n\n已知大学中有 #cf_span[n] 个学生小组，#cf_span[m] 位教授，以及 #cf_span[a] 间教室可用于授课。此外，你有一个大小为 #cf_span[n × m] 的二维数组，其中第 #cf_span[i] 行第 #cf_span[j] 列的数值表示教授 #cf_span[j] 每周必须与第 #cf_span[i] 个学生小组进行的课程数量。你输出的课程表必须满足上述数组的要求。\n\n课程表还需满足以下条件：单个教授在同一时间不能教授超过一节课；同样，单个学生小组在同一时间也不能参加超过一节课。\n\n定义教授和学生小组的 _疲劳度_ 函数，记为 #cf_span[f]。\n\n对于单个教授，其疲劳度计算方式如下：观察该教授在每个 #cf_span[6] 个教学日中所教授的课程。设 #cf_span[x] 为该教授在第 #cf_span[i] 天首次授课的课程编号，#cf_span[y] 为该教授在第 #cf_span[i] 天最后一次授课的课程编号，则需将值 #cf_span[(2 + y - x + 1)·(2 + y - x + 1)] 加入该教授的疲劳度。如果该教授在第 #cf_span[i] 天没有课程，则不增加其疲劳度。\n\n对于单个学生小组，其疲劳度的计算方式类似：观察该小组在每个 #cf_span[6] 个教学日中的课程。设 #cf_span[x] 为该小组在第 #cf_span[i] 天首次上课的课程编号，#cf_span[y] 为该小组在第 #cf_span[i] 天最后一次上课的课程编号，则需将值 #cf_span[(2 + y - x + 1)·(2 + y - x + 1)] 加入该小组的疲劳度。如果该小组在第 #cf_span[i] 天没有课程，则不增加其疲劳度。\n\n因此，函数 #cf_span[f] 的值等于所有 #cf_span[n] 个学生小组和所有 #cf_span[m] 位教授的总疲劳度。\n\n你的任务是设计一个课程表，使函数 #cf_span[f] 的值最小化。\n\n出题方已准备了一个该问题的解决方案。对于每个测试用例，你将获得一定分数，该分数等于出题方方案的 #cf_span[f] 值除以你的方案的 #cf_span[f] 值，再乘以 #cf_span[100]（即你的方案找到的疲劳度越小，得分越高）。换句话说，若出题方方案的 #cf_span[f] 值为 #cf_span[p]，你的方案为 #cf_span[q]，则你将获得 #cf_span[100·p / q] 分（注意，得分是一个实数）。所有测试用例的得分将相加，目标是获得尽可能多的分数。\n\n第一行包含三个整数 #cf_span[n], #cf_span[m] 和 #cf_span[a]（#cf_span[1 ≤ n, m, a ≤ 60]）——学生小组数、教授数和教室数。\n\n接下来的 #cf_span[n] 行，每行包含 #cf_span[m] 个从 #cf_span[0] 到 #cf_span[24] 的整数，第 #cf_span[i] 行第 #cf_span[j] 个数表示教授 #cf_span[j] 必须与第 #cf_span[i] 个学生小组进行的课程数量。\n\n保证每位教授和每个学生小组每周的课程总数不超过 #cf_span[24]。同时保证每周课程总数不超过基于教室数量所能安排的最大课程数的 #cf_span[75]%。所有测试用例均至少存在一个满足所有条件的课程表。\n\n第一行输出函数 #cf_span[f] 的最小化值。\n\n然后输出一个空行。\n\n接着按学生小组编号递增顺序输出每个小组的课程表。对每个学生小组，输出 #cf_span[7] 行，每行包含 #cf_span[6] 个数字。设第 #cf_span[i] 行第 #cf_span[j] 列的数为 #cf_span[x]。如果在第 #cf_span[j] 天该小组没有第 #cf_span[i] 节课，则 #cf_span[x] 必须为 0；否则 #cf_span[x] 必须为与该小组在该节课授课的教授编号。\n\n同时进行的课程数不得超过教室数 #cf_span[a]。\n\n用空行分隔不同小组的课程表描述。\n\n在比赛主要阶段（一周内），你的程序将在 #cf_span[100] 个预测试用例上进行评测。前 #cf_span[10] 个预测试用例可通过链接 http://assets.codeforces.com/files/vk/vkcup-2017-wr2-materials-v1.tar.gz 下载。\n\n比赛结束后（即开赛一周后），你提交的最后一个得分正数的解决方案将被选中用于在扩展的最终测试用例上运行。\n\n## Input\n\n第一行包含三个整数 #cf_span[n], #cf_span[m] 和 #cf_span[a]（#cf_span[1 ≤ n, m, a ≤ 60]）——学生小组数、教授数和教室数。接下来的 #cf_span[n] 行，每行包含 #cf_span[m] 个从 #cf_span[0] 到 #cf_span[24] 的整数，第 #cf_span[i] 行第 #cf_span[j] 个数表示教授 #cf_span[j] 必须与第 #cf_span[i] 个学生小组进行的课程数量。保证每位教授和每个学生小组每周的课程总数不超过 #cf_span[24]。同时保证每周课程总数不超过基于教室数量所能安排的最大课程数的 #cf_span[75]%。所有测试用例均至少存在一个满足所有条件的课程表。\n\n## Output\n\n第一行输出函数 #cf_span[f] 的最小化值。然后输出一个空行。接着按学生小组编号递增顺序输出每个小组的课程表。对每个学生小组，输出 #cf_span[7] 行，每行包含 #cf_span[6] 个数字。设第 #cf_span[i] 行第 #cf_span[j] 列的数为 #cf_span[x]。如果在第 #cf_span[j] 天该小组没有第 #cf_span[i] 节课，则 #cf_span[x] 必须为 0；否则 #cf_span[x] 必须为与该小组在该节课授课的教授编号。同时进行的课程数不得超过教室数 #cf_span[a]。用空行分隔不同小组的课程表描述。\n\n[samples]\n\n## Note\n\n在比赛主要阶段（一周内），你的程序将在 #cf_span[100] 个预测试用例上进行评测。前 #cf_span[10] 个预测试用例可通过链接 http://assets.codeforces.com/files/vk/vkcup-2017-wr2-materials-v1.tar.gz 下载。比赛结束后（即开赛一周后），你提交的最后一个得分正数的解决方案将被选中用于在扩展的最终测试用例上运行。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, m, a \\in \\mathbb{Z}^+ $ denote the number of student groups, professors, and classrooms, respectively.  \nLet $ C \\in \\mathbb{Z}^{n \\times m} $ be the demand matrix, where $ C_{i,j} $ is the number of classes professor $ j $ must teach with group $ i $ per week.  \nLet $ D = 6 $ be the number of educational days per week.  \nLet $ L = 7 $ be the maximum number of class slots per day (numbered 1 to 7).  \n\nA schedule is a mapping $ S: \\{1, \\dots, n\\} \\times \\{1, \\dots, D\\} \\times \\{1, \\dots, L\\} \\to \\{0\\} \\cup \\{1, \\dots, m\\} $, where $ S_{i,d,k} = j $ means group $ i $ has a class with professor $ j $ on day $ d $ at slot $ k $, and $ S_{i,d,k} = 0 $ means no class.  \n\n**Constraints**  \n1. **Demand satisfaction**: For each group $ i $ and professor $ j $,  \n   $$\n   \\sum_{d=1}^D \\sum_{k=1}^L \\mathbf{1}_{S_{i,d,k} = j} = C_{i,j}\n   $$  \n2. **Professor uniqueness**: For each professor $ j $, day $ d $, and slot $ k $, at most one group is assigned:  \n   $$\n   \\left| \\left\\{ i \\in \\{1,\\dots,n\\} \\mid S_{i,d,k} = j \\right\\} \\right| \\leq 1\n   $$  \n3. **Group uniqueness**: For each group $ i $, day $ d $, and slot $ k $, at most one professor is assigned:  \n   $$\n   \\left| \\left\\{ j \\in \\{1,\\dots,m\\} \\mid S_{i,d,k} = j \\right\\} \\right| \\leq 1\n   $$  \n4. **Classroom capacity**: For each day $ d $ and slot $ k $, the number of concurrent classes does not exceed $ a $:  \n   $$\n   \\sum_{i=1}^n \\mathbf{1}_{S_{i,d,k} \\neq 0} \\leq a\n   $$  \n5. **No overlapping assignments**: For each $ (i,d) $, the non-zero $ S_{i,d,k} $ form a contiguous interval (no gaps).  \n\n**Fatigue Function**  \nFor each professor $ j $, define for each day $ d $:  \n- Let $ x_{j,d} = \\min \\{ k \\in \\{1,\\dots,L\\} \\mid \\exists i, S_{i,d,k} = j \\} $ if professor $ j $ has classes on day $ d $, else undefined.  \n- Let $ y_{j,d} = \\max \\{ k \\in \\{1,\\dots,L\\} \\mid \\exists i, S_{i,d,k} = j \\} $ if professor $ j $ has classes on day $ d $, else undefined.  \n- If professor $ j $ has no class on day $ d $, contribution is 0.  \n- Otherwise, fatigue contribution: $ (2 + y_{j,d} - x_{j,d} + 1)^2 = (y_{j,d} - x_{j,d} + 3)^2 $.  \n\nSimilarly for each group $ i $:  \n- Let $ x_{i,d} = \\min \\{ k \\in \\{1,\\dots,L\\} \\mid S_{i,d,k} \\neq 0 \\} $ if group $ i $ has classes on day $ d $, else undefined.  \n- Let $ y_{i,d} = \\max \\{ k \\in \\{1,\\dots,L\\} \\mid S_{i,d,k} \\neq 0 \\} $ if group $ i $ has classes on day $ d $, else undefined.  \n- Fatigue contribution: $ (y_{i,d} - x_{i,d} + 3)^2 $ if classes exist, else 0.  \n\nTotal fatigue:  \n$$\nf = \\sum_{j=1}^m \\sum_{d=1}^D (y_{j,d} - x_{j,d} + 3)^2 \\cdot \\mathbf{1}_{\\text{prof } j \\text{ has class on day } d} + \\sum_{i=1}^n \\sum_{d=1}^D (y_{i,d} - x_{i,d} + 3)^2 \\cdot \\mathbf{1}_{\\text{group } i \\text{ has class on day } d}\n$$\n\n**Objective**  \nMinimize $ f $ subject to the above constraints.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF775A","tags":[],"sample_group":[["3 3 1\n1 0 0\n0 1 0\n0 0 1","54\n\n1 0 0 0 0 0 \n0 0 0 0 0 0 \n0 0 0 0 0 0 \n0 0 0 0 0 0 \n0 0 0 0 0 0 \n0 0 0 0 0 0 \n0 0 0 0 0 0 \n\n0 0 0 0 0 0 \n2 0 0 0 0 0 \n0 0 0 0 0 0 \n0 0 0 0 0 0 \n0 0 0 0 0 0 \n0 0 0 0 0 0 \n0 0 0 0 0 0 \n\n0 0 0 0 0 0 \n0 0 0 0 0 0 \n3 0 0 0 0 0 \n0 0 0 0 0 0 \n0 0 0 0 0 0 \n0 0 0 0 0 0 \n0 0 0 0 0 0"],["3 1 1\n1\n1\n1","52\n\n1 0 0 0 0 0 \n0 0 0 0 0 0 \n0 0 0 0 0 0 \n0 0 0 0 0 0 \n0 0 0 0 0 0 \n0 0 0 0 0 0 \n0 0 0 0 0 0 \n\n0 0 0 0 0 0 \n1 0 0 0 0 0 \n0 0 0 0 0 0 \n0 0 0 0 0 0 \n0 0 0 0 0 0 \n0 0 0 0 0 0 \n0 0 0 0 0 0 \n\n0 0 0 0 0 0 \n0 0 0 0 0 0 \n1 0 0 0 0 0 \n0 0 0 0 0 0 \n0 0 0 0 0 0 \n0 0 0 0 0 0 \n0 0 0 0 0 0"],["5 7 10\n1 3 6 0 1 2 4\n0 3 0 6 5 1 4\n3 5 1 2 3 2 4\n2 3 1 1 4 1 2\n2 4 3 2 4 3 2","1512\n\n0 0 6 0 0 2 \n0 7 6 3 3 7 \n3 1 2 3 2 7 \n3 7 0 0 0 0 \n5 3 0 0 0 0 \n0 0 0 0 0 0 \n0 0 0 0 0 0 \n\n0 0 4 0 7 6 \n4 5 7 4 5 5 \n7 2 4 4 5 5 \n7 2 0 4 0 0 \n0 2 0 0 0 0 \n0 0 0 0 0 0 \n0 0 0 0 0 0 \n\n4 0 7 2 5 7 \n5 0 2 5 7 1 \n2 4 1 2 7 1 \n2 3 0 0 0 0 \n0 6 0 0 0 0 \n0 6 0 0 0 0 \n0 0 0 0 0 0 \n\n0 0 0 5 3 5 \n0 2 4 7 2 6 \n0 5 7 0 0 0 \n1 5 1 0 0 0 \n2 0 0 0 0 0 \n0 0 0 0 0 0 \n0 0 0 0 0 0 \n\n0 0 5 7 2 3 \n0 1 3 2 6 3 \n5 7 6 5 6 4 \n5 4 2 2 0 0 \n1 0 0 0 0 0 \n0 0 0 0 0 0 \n0 0 0 0 0 0"]],"created_at":"2026-03-03 11:00:39"}}