← 返回题目列表

AtCoder · asprocon9_a

A. 轮班安排

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

故事

您已加入一个改进工厂生产计划的项目。目前,工厂内的所有机器仅在工作日的 09:00 - 12:00 和 13:00 - 18:00 之间运行。但根据具体情况,目前使用的固定运行时间可能并不适合所有机器。可能会出现这样的情况:一些机器没有足够的时间来处理所有给定的工作,而另一些机器则无事可做,它们的运行时间被浪费了。你的任务是开发 调整程序,根据情况调整每台机器的运行时间。

幸运的是, 调度程序 根据运行时间生成生产计划的 已存在。看来可以通过调度程序来判断你的程序的输出是否正确。

请注意,调度程序的算法将来可能会得到改进。此外,如果调整方案效果良好,人们可能希望将其应用到生产不同产品的其他工厂。因此,看来你的算法应该独立于调度程序的实现和工厂的环境。

为此,您决定根据调度程序生成的生产计划的一些评估指标而不是生产计划本身来调整调整程序的输出。

请构建与调度程序交互的调整程序,并建议每台机器的最佳运行时间。

问题陈述

在工厂里,有 M 机器。机器编号从 1 to M。生产计划的目标期为 X 周。调整程序必须确定每个的运行时间 M 机器中的每个 X 周。

此外,还有 N 订单应在 X 周。订单编号从 1 to N。订单 i 包含以下信息。

  • 截止日期 d_i
  • 生成它所需的步骤量 J_i
  • 对于每个 j = 1, 2, \dots, J_i, j第一步由机器处理 r_{i,j} 并且需要时间 t_{i,j} 进行处理

截止时间表示为自第一天 0:00 起经过的秒数。例如,如果 d_i = 64800 (= 18 \times 60 \times 60),表示截止时间为首日18:00。另外,所有处理时间的单位是秒。

虽然订单数据被传递到调度程序,但它不被传递到调整程序。

调整方案详情

机器的运行时间可以是以下运行模式之一。

  • 操作模式 1:不操作
  • 运营模式2:9:00-12:00
  • 运营模式3:13:00-18:00
  • 运营模式4:9:00-12:00 + 13:00-18:00
  • 运营模式5:9:00-12:00 + 13:00-20:00
  • 运营模式6:9:00-12:00 + 13:00-22:00
  • 运营模式7:9:00-12:00 + 13:00-24:00
  • 运营模式8:9:00-12:00 + 13:00-26:00
  • 运营模式9:9:00-12:00 + 13:00-28:00

每周允许为每台机器设置不同的运行模式。一周由 5 天工作日和 2 天周末组成。还允许在工作日和周末设置不同的运行模式。但同一台机器在同一周的工作日必须有相同的运行模式;在同一周的周末也必须有相同的运营模式。

每周每台机器的运行模式可以表示为 M 字符串 P_1, \dots, P_M。在这里,每一个 P_m 是一个长度为的字符串 2X 仅由 1, 2, ..., 9。对于每个 w\ (1 \le w \le X),

  • 的 2w-1- 第一个字符 P_m 代表机器工作日运行模式 m 周内 w.
  • 的 2w- 第一个字符 P_m 代表机器周末运行模式 m 周内 w.

让机器运转的成本很高。相同的运营模式在工作日和周末的成本可能会有所不同。不同的机器也可能有不同的运行成本。具体来说,需要花费 costA_{m,k} 操作机器 m 处于操作模式 k 工作日,费用 costB_{m,k} 周末。

虽然希望降低成本,但违反期限是不允许的。因此,您的目标是在按时处理订单的同时尽可能少地操作机器。调整程序不知道订单数据。订单是否迟到由调度程序判断。

此外,由于如果操作模式改变频繁,则很难安排操作员,所以改变操作模式存在限制。具体来说,经营模式的变化不应超过 C 次。这里,改变运行模式是指本周的工作日运行模式与下周的工作日运行模式不同,或者,当前周的周末运行模式与下周的周末运行模式不同。

为了找到操作模式,调整程序与调度程序按照以下工作流程一起工作。稍后将描述调度程序的细节。

  1. 调整程序输出操作模式
  2. 调度程序根据调整程序的输出和订单数据生成生产计划
  3. 调度程序计算生成的生产计划的考核指标
  4. 调度程序返回评价指标

将重复上述工作流程 E 次。该题的得分将是该题得分中最好的得分 E 输出。

调度程序详情

调度程序根据操作模式和订单数据生成生产计划。操作模式是调整程序的输出。顺序数据是预先确定的并且在整个测试用例中是固定的。

的 j顺序的第一步 i 被称为 工作(i, j)。调度程序决定工作的开始和结束时间 (i, j)。由于处理工作的过程中可能会有休息时间,因此调度程序还确定何时暂停或恢复工作。

调度程序生成的生产计划满足以下两个约束。

  • If j > 1,工作 (i, j) 只能下班后开始 (i, j - 1) 启动。
  • If j > 1,工作 (i, j) 只能下班后结束 (i, j - 1) 结束。

此问题中的工厂通过几个步骤生产产品。各步骤之间通过的零件和产品称为中间产品。经过某一步骤制成的中间产品可以逐一进入下一步。中间产品通过后即可立即开始下一步加工。

订单中所需的产品数量通常以“1,000 个产品 A”的形式指定。基于上述原因,开工时间 (i, j) 可能早于下班时间 (i, j-1).

为简单起见,调度程序假设所有订单中所需的产品数量足够大,并且传递中间产品所需的时间非常小,可以忽略不计。在这种假设下,多个后续步骤可以同时启动它们的过程(只要机器是空的)。这对应于第一个约束。此外,由于在上一步结束之前有一个步骤完成是很奇怪的,所以设置第二个约束来防止这种生产计划。

调度程序的算法大致如下伪代码所示。请注意,由于这对于暂停和恢复工作的情况来说是不够的,因此实际算法会根据暂停时间自动划分工作。详细信息请参考分布式源代码。 (解决这个问题不需要了解细节)

  1. 一周后 X + 1,为每台机器附加足够长的虚拟操作时间
  2. 对于 i = 1, 2, \dots, N 和步骤 j = 1, 2, \dots, J_i,按字典顺序递增处理以下内容 (i, j)
    1. If j > 1 然后让 a, b 是工作的开始时间和结束时间 (i, j-1)。如果 j = 1 然后让 a = -1, b = 0
    2. 如果有已计划在机器上加工的工件 r_{i,j},设这些作品的最大结束时间为 a' 和 c = \max(a, a')。否则,让 c = a.
    3. 让 d 是最小值 x 这样“正好有 t_{i,j} 机器运行时间 r_{i,j} 及时 [c, x]“。 (由于存在虚拟操作时间,因此 x 必须存在)
    4. 确定 c', d',工作开始时间和结束时间 (i, j),如下
      • If d \ge b 然后让 c' = c, d' = d
      • If d < b,然后让 c' 是最小值 x 这样“正好有 t_{i,j} 机器运行时间 r_{i,j} 及时 [x, b]“和 d' = b

订单 如果最后一步的结束时间严格晚于 i ,则判断为延迟 d_i。如果结束时间落在虚拟运行时间内,也被判断为延迟。

调度程序的反馈

调度程序会返回以下评价指标。

  • D: 延迟订单数量
  • RD_{m,w}: 机器的负载率 m 本周 w
  • RO_{m,w}: 机器上处理的延迟工作数量 m 本周 w

负载系数 是每周每台机器的(总处理时间)/(总运行时间)。它是一个介于 0 和 1.

延误的工程 是延迟订单的作品。也就是说,工作 (i, j) 是延迟工作意味着订单 i 已延迟。如果延迟的工作在数周内处理,则计入所有已处理的周数。

调度程序的行为示例

示例 1

  • X = 1, M = 3, N = 1
  • 所有机器 1, 2, 3 按照运行模式运行 41 (仅工作日9-12点和13-18点运行)
  • J_1 = 3, r_{1,1} = 1, r_{1,2} = 2, r_{1,3} = 3。每个步骤需要4个小时来处理

根据上述设置,每项工作从第一天9:00开始,到14:00结束。由于机器在 12:00 至 13:00 之间不运行,因此 9:00 至 14:00 之间正好有 4 个小时的运行时间。

对于每台机器,由于总处理时间为 4 小时,总运行时间为 40 小时,因此负载系数为 4/40 = 0.1.

示例 2

  • X = 1, M = 3, N = 4
  • 机器1、3的运行模式是 21 (仅工作日9:00-12:00运行)
  • 机器2的运行模式是 31 (仅工作日13:00-18:00运行)
  • J_1 = 2, r_{1,1} = 1, r_{1,2} = 3
  • J_2 = 2, r_{2,1} = 2, r_{2,2} = 3
  • J_3 = 2, r_{3,1} = 1, r_{3,2} = 3
  • J_4 = 1, r_{4,1} = 3
  • 每个步骤需要 5 小时处理

根据上述设置,调度程序生成以下生产计划。

  • 工作 (1, 1) 第一天9:00到12:00处理,第二天9:00到11:00处理。
  • 工作 (1, 2) 第一天9:00到12:00处理,第二天9:00到11:00处理。
  • 工作 (2, 1) 首日13:00至18:00处理
  • 工作 (2, 2) 处理时间为第二天11:00至12:00、第三天9:00至12:00、第四天9:00至10:00
  • 工作 (3, 1) 处理时间为第二天11:00至12:00、第三天9:00至12:00、第四天9:00至10:00
  • 工作 (3, 2) 第四天10:00至12:00、第五天9:00至12:00处理
  • 工作 (4, 1) 在虚拟操作时间内进行处理。

矩形代表作品。矩形中的数字代表其订单 ID。灰色部分代表空闲运行时间。这里,第 6 天和第 7 天被省略,因为它们没有运行时间。

例如,工作使用的机器 1 (1, 1) 仅在早上运营。前3个小时安排在第一天,其余的安排在第二天。其他工作也计划尽早启动。

由于3号机一直被占用到第五天,所以工作 (4, 1) 计划在虚拟操作时间内处理。

截止日期如下。 (因为 86400 = 24 \times 60 \times 60, d_1 等于第四天的0:00,也就是说必须在前三天完成)

  • d_1 = 86400 \times 3
  • d_2 = 86400 \times 4
  • d_3 = 86400 \times 4
  • d_4 = 86400 \times 5

在这种情况下,评价指标如下。

  • D = 2 (订单 3, 4 迟到了)
  • RD_{1,1} = 10/15 = 0.666\dots
  • RD_{2,1} = 5/25 = 0.2
  • RD_{3,1} = 15/15 = 1
  • RO_{1,1} = 1 (迟到的工作是工作 (3, 1))
  • RO_{2,1} = 0
  • RO_{3,1} = 1 (迟到的工作是工作 (3, 2))

请注意,虽然订单 4 迟到了,上班 (4, 1) 任何一周都不计为延迟工作。一般来说,如果工作 (i, j) 未计划在任何 X 周,延误将不计入任何 X 订购周数 i 将被视为延迟订单。

示例3

此示例是上面伪代码未涵盖的特殊情况。如果根据伪代码计算生产计划,则工作结束时间 (1, 2) 将超出机器的运行时间。这个例子展示了用于判断的实际算法如何处理这种情况。

  • X = 1, M = 2, N = 1
  • 机器1的运行模式是 21 (仅工作日9:00-12:00运行)
  • 机器2的运行模式是 31 (仅工作日13:00-18:00运行)
  • J_1 = 2, r_{1,1} = 1, r_{1,2} = 2
  • 每个步骤需要 5 小时处理

在这种情况下,生产计划如下。

  • 工作 (1, 1) 第一天9:00至12:00处理,第二天9:00至11:00处理
  • 工作 (1, 2) 第一天15:00至18:00处理,第二天13:00至15:00处理

上班以来 (1, 2) 在机器2上加工,只能在下午加工。虽然下午有5个小时的作业时间,但第一天只处理了3个小时的前期工作。所以工作时间只有3个小时 (1, 2) 可以安排在第一天。剩下的2个小时的工作时间安排到第二天。

虽然也可以安排在第一天的 13:00-16:00 或 14:00-17:00,但只要结束时间相同,安排程序会尽可能晚地开始工作。

约束

输入满足以下约束。

  • X, M, C, E 是整数。
  • 8 \leq X \leq 16
  • 10 \leq M \leq 20
  • 2 \leq C \leq 8
  • E \in {50, 100, 300}
  • costA_{m,k}, costB_{m,k} 是非负整数 (1 \le m \le M, 1 \le k \le 9).
  • costA_{m,k} \le costA_{m,k+1} (1 \le m \le M, 1 \le k < 9)
  • costB_{m,k} \le costB_{m,k+1} (1 \le m \le M, 1 \le k < 9)
  • \sum_{m}(costA_{m,9} + costB_{m,9}) < 10^{10}

判断程序使用的订单数据满足以下约束。

  • 0 < d_i \le 86400 \times (7 \times X - 1)
  • r_{i,j} < r_{i,j+1} (1 \le i \le N, 1 \le j < J_i)
  • 2880 \le t_{i,j}
  • 保证存在操作模式,使得调度程序无延迟地输出生产计划

每个测试用例的顺序数据都是固定的。也就是说,所有的数据都使用相同的数据。 E 次计划。

输入和输出

最初, 黑板上写着 X (周数), M (机器数量), C (运行模式变化的最大次数), 给出了 E (交互次数)。

X M C E
costA_{1,1} costB_{1,1}
\vdots
costA_{1,9} costB_{1,9}
costA_{2,1} costB_{2,1}
\vdots
costA_{2,9} costB_{2,9}
\vdots
costA_{M,1} costB_{M,1}
\vdots
costA_{M,9} costB_{M,9}

读取上述输入后,处理以下内容 E 互动。您的程序应在以下时间后终止 E-次交互。

操作模式的输出

输出 M 字符串 P_1, \dots, P_M 以下列格式表示操作模式。

P_{1}
P_{2}
\vdots
P_{M}

不要忘记将输出刷新到标准输出。

评价指标的输入

调度程序按以下格式返回评价指标。负载系数 RD_{m,w} 小数点后最多 3 位数字。

score V D
RD_{1,1} RO_{1,1}
\vdots
RD_{1,X} RO_{1,X}
\vdots
RD_{M,1} RO_{M,1}
\vdots
RD_{M,X} RO_{M,X}

V 是违反限制的更改数 C。具体来说,对于每个 m (1 \le m \le M),让 x_m 的金额 j (1 \le j \le 2X-2) 这样 P_{m,j} \neq P_{m,j+2},那么 V = \sum_m \max(0, x_m - C).

score 是计划的分数。如果出现以下情况 D > 0 or V > 0,分数等于 0。否则,分数等于 \mathrm{round}(10^{9} \times (10 - \log_{10}(cost)))。在这里, cost 根据运营模式的成本计算如下 cost = \lfloor \frac 1 X \sum_{m,w} (costA_{m,P_{m,2w-1}} + costB_{m,P_{m,2w}}) \rfloor.

如果输出格式不正确,则不能保证判断程序正确运行。特别是,不保证提交的判决一定会得到批准 WA.

评分

测试用例的得分 AC 判决将是最高分 E 互动。测试用例的得分为非AC 判决将是 0.

提交的分数是每个测试用例的总分。

有 50 临时测试中的测试用例,以及 3000 系统测试中的测试用例。系统测试包含 1000 每个测试用例 E = 50, 100, 300.

种子 (systemtest_seed.zip;用于生成测试用例的sha256=0ef661053146f225ceb093bce97faa992138482df5ef1f3778ce63467e507d09)将在比赛结束后发布。

每次运行的执行时间可能略有不同。此外,由于系统测试同时执行大量执行,因此观察到与临时测试相比,执行时间增加了几个百分点。由于这些原因,非常接近期限的提交可能会导致 TLE 在系统测试中。请测量程序中的执行时间以终止进程,或确保有足够的执行时间。

测试用例生成摘要

详情请参阅gen.h。

生成机器、操作时间、步骤和产品

  1. 确定 E by seed\ \mathrm{mod}\ 3。也就是说, E = 50 当 seed \equiv 0 \ (\mathrm{mod}\ {3}), E = 100 当 seed \equiv 1 \ (\mathrm{mod}\ {3}), E = 300 当 seed \equiv 2 \ (\mathrm{mod}\ {3}).
  2. 确定 X, M, C, I, L 在他们的约束下均匀随机。在这里,
    • I 是产品的类型数量 (30 \le I \le 300)
    • L 是步骤的类型数 (1 \le L \le M)
  3. 确定 ML_{m},机器的步骤 m 属于,因此对于所有 m \ge 2, ML_{m-1} \le ML_{m}。 (此外, 1 \le ML_{m} \le L)
  4. 统一随机初始化3~8步的运行模式。对于每台机器,设置所有操作模式 X 周是一样的。
  5. 每周随机改变每台机器4.中确定的操作模式。
  6. 设机器需求为每台机器的总运行时间,步骤需求为每个步骤的总运行时间。
  7. 确定每个产品的步骤数。随机选择步骤以及每个步骤需要通过的机器。按照与步骤需求和机器需求相对应的比例来选择步骤和机器。按索引对选定的机器进行排序。产品需要通过的机器序列等于排序后的索引。

生成订单数据

最初,让 i = 1。重复以下过程生成订单数据。

  1. 随机选择一个产品作为订单的目标产品 i。让 J_i 是它需要通过的机器数量, r_{i,j} 是 j该产品通过的第机器。
  2. 确定 t_{i,j},下单所需时间 i 在每个步骤中。
  3. 安排订单 i 由调度程序使用的相同调度算法。
  4. 让 t 为订单最后一步的结束时间 i。处理以下内容
    1. If t \le 86400 \times (7 \times X - 1),让 d_i = t,添加订单 i 到订单数据,增加 i 增 1。
    2. 否则,结束订单数据生成,不添加订单 i 到订单数据。

由于这里使用的调度算法与调度程序使用的调度算法相同,因此保证存在按时生成所有订单的操作模式。

生成运营模式的成本

22:00-28:00 之间的时间段被定义为夜班。
定义 rand(x,y) 作为生成大于或等于的实数的函数 x 且小于 y 均匀随机。

  1. 对于每台机器 m,确定 NW_{m} (所需操作员数量), DC_{m} (白班计时工资), NC_{m} (夜班计时工资), costRatio_{m} (相对于运行时间的成本增加率)
  2. 万一 3 \le k,让 Dsum_{k} 是白天的总运行时间, Nsum_{k} 为运行模式下夜间总运行时间 k。工作日机器成本 m 处于操作模式 k is (NW_{m} \times (DC_{m} \times Dsum_{k} + NC_{m} \times Nsum_{k}) ) \times costRatio_m^{Dsum_{k} + Nsum_{k}}.
  3. 平日机器成本 m 处于操作模式 2 is round(c_3 \times rand(0.5,1)),其中 c_3 是机器在运行模式下的成本 3.
  4. 平日机器成本 m 处于操作模式 1 is round(rand(0.0,c_2)),其中 c_2 是机器在运行模式下的成本 2.
  5. 周末费用等于工作日费用乘以 0.48.

工具

您可以下载以下工具。我们已经检查了分布式源代码可以通过g++-9.4.0编译。

  • Visualizer/dist/index.html:可视化工具。请用浏览器打开。点击页面中的信息按钮即可查看信息。
    • 源代码位于 Visualizer/src 下。 你可以通过以下方式构建它 npm install && npm run build 如果您要修改它。
  • generator.cpp:生成输入数据的程序。它从标准输入读取参数并生成测试用例。
  • parameters_50.txt:生成器输入的示例。 (法官使用不同的种子来生成测试用例)
  • in/*.txt:输入数据样本。这是由parameters_50.txt 生成的。
  • Judge.cpp:用于判断提交内容的程序。
  • runner.py:在 MSVC 等环境中用于判断程序的帮助程序脚本,其中 fork() 或其他无效。
  • sample.cpp:C++示例代码。

generator.cpp的用法及示例

编译 generator.cpp 并将参数文件传递给它以生成测试用例。

需要编译 Problem.cpp 预先并链接它。例如,运行以下命令。

g++ --std=c++2a -c -o Problem.o Problem.cpp
g++ --std=c++2a -o generator Problem.o generator.cpp

之后,在所在目录中运行以下脚本 放入 generator 和 parameters_50.txt 文件夹下生成50个测试用例 input。 (生成的测试用例与下载的测试用例相同)

mkdir -p input
cd input
../generator < ../parameters_50.txt

请注意,在 Windows 环境中(例如 cmd.exe), / 应替换为 \ 以防止错误。

judge.cpp的用法及示例

如果您在 Windows 环境中执行,另请阅读“runner.py 的用法和示例”。

编译 judge.cpp 并传递命令以作为命令行参数执行解决方案程序。

g++ --std=c++2a -c -o Problem.o Problem.cpp
g++ --std=c++2a -o judge Problem.o judge.cpp
./judge ./your_solution < input/0000.txt > out0000.txt

judge 会将可视化器的数据输出到标准输出。要可视化输出,请传递 执行上述命令后,将 out0000.txt 发送到可视化工具。标准错误包含来自判断程序的消息以及测试用例的最后得分。

如果需要参数来执行您的解决方案,请将该命令用引号引起来。

./judge "python3 your_solution.py" < input/0000.txt > out0000.txt

runner.py的用法和示例

如果judge.cpp是用宏编译的 ASPROCON9_USE_RUNNER 被定义,我们希望您使用 runner.py 运行它。

使用 MSVC 时, ASPROCON9_USE_RUNNER 将自动定义(judge.cpp 第 10-12 行)。如果您打算在其他情况下使用 runner.py,请使用命令行参数定义宏或修改 Judge.cpp。

要通过 runner.py 执行判断程序,请按上述顺序指定“判断程序”、“输入文件”、“输出文件”、“运行解决方案的命令”。

python3 runner.py ./judge input/0000.txt out0000.txt ./your_solution

输出数据包含可视化工具的数据。要可视化输出,请在执行上述命令后将 out0000.txt 传递到可视化工具。标准错误包含来自判断程序的消息以及测试用例的最后得分。

如果需要命令行参数来执行您的解决方案,只需将它们附加到命令末尾即可。请注意,如果用引号将它们括起来,它将无法正确执行。

python3 runner.py ./judge input/0000.txt out0000.txt python3 your_solution.py