P15273 [Google Hashcode 2021 Finals] Software Engineering at Scale

#### 介绍 谷歌将其绝大多数代码存储在一个单一的大型代码库中，包含数十亿行代码。截至 2016 年，超过 25,000 名软件工程师为其做出贡献，改进现有服务并添加酷炫的新功能，以满足用户需求。 随着代码库规模的增大和谷歌软件工程师数量的增加，安排工程师的工作变得具有挑战性，以便他们能够高效工作并推出让用户满意的功能。 #### 目标 给定一些**服务**、一些**二进制文件**以及一组要实现的**功能**，决定**工程师**应该如何安排他们的工作，以交付尽可能让用户满意的功能。

#### 架构 在本问题中，我们考虑功能、服务和二进制文件： - **功能**是谷歌产品面向用户的功能。例如：YouTube 中的视频播放列表或 Google 搜索中的天气预报。 - **服务**是在谷歌数据中心运行的程序。例如：YouTube 可能有一个负责存储用户视频集合的服务。 - **二进制文件**是一组为了效率而组合在一起运行的服务。例如：在同一二进制文件中运行的服务可以共享资源，如数据库连接。 ##### 功能 每个功能描述如下： - 它所依赖的服务。 - 受益于该功能（当它发布时）的每日用户数量。 一旦一个功能在其依赖的所有服务中实现，它就会立即发布，用户开始受益于它。 ##### 服务和二进制文件 每个服务恰好属于一个二进制文件，但一个二进制文件可以包含多个服务。最初每个二进制文件至少包含一个服务，但后来二进制文件变空也是有效的。服务可以在二进制文件之间移动，并且可以根据需要创建新的二进制文件。 在实现一个功能时，工程师利用了一个二进制文件包含多个服务这一事实——工程师可以一次在给定二进制文件中的所有相关服务中实现给定的功能。 :::align{center}  ::: 图 1. 有两个功能（foo 和 bar），五个服务（sa、sb、sc、sd、se），三个二进制文件（0、1 和 2），以及 2 名工程师（G0 和 G1）。二进制文件 0 运行一个服务（se），二进制文件 1 运行两个（sa 和 sc），二进制文件 2 也运行两个（sb 和 sd）。要实现功能 foo，工程师需要处理服务 sb、sc 和 sd，这意味着他们需要处理两个二进制文件（1 和 2）。要实现功能 bar，工程师需要处理功能 sa 和 sc，因此只需要处理二进制文件 1。 #### 调度工作 你的目标是为工程师分配工作以实现功能，以便尽可能多的用户受益于它们。 谷歌有 $G$ 名工程师可以实现这些功能。在每一天，工程师可以开始以下任何一项任务： - 在二进制文件 $B_j$ 的服务中实现功能 $F_i$。 - 将服务 $S_i$ 从二进制文件 $B_j$ 移动到另一个二进制文件 $B_k$。 - 创建一个新的空二进制文件。 - 等待若干天。 这些任务都不能被中断，这意味着一旦工程师开始一项任务，他们将在该任务的持续时间内继续工作。 对一个二进制文件中运行的一组服务进行更改比对分散在多个二进制文件中的服务进行更改更容易。另一方面，许多工程师在同一个二进制文件中处理服务会相互干扰，减慢工作速度。下面将对此进行更详细的描述。 ##### 任务：实现一个功能 工程师可以选择任何二进制文件 $B_j$，并一次在该二进制文件的所有相关服务中实现功能 $F_i$。 如果工程师在二进制文件 $B_j$ 上工作以实现功能 $F_i$，这项工作将需要 $D_{F_i} + R_{B_j} + C_{B_j}$ 天，其中： - $D_{F_i}$ 是功能 $F_i$ 的难度， - $R_{B_j}$ 是 $B_j$ 中的服务总数（包括与 $F_i$ 无关的服务），以及 - $C_{B_j}$ 是在这项工作的第一天已经在 $B_j$ 上处理功能的工程师数量。 任务完成后，功能 $F_i$ 将在 $B_j$ 的所有相关服务中实现。 多名工程师可以在不同的二进制文件中实现相同的功能，但一次只能有一名工程师在一个二进制文件中实现特定功能。如果两名工程师在同一天开始在同一二进制文件上工作（实现两个不同的功能），**提交文件中列出的较早的那位**首先开始，并计入第二名工程师开始工作时在该二进制文件上工作的工程师数量。 :::align{center}   ::: 图 2. (a) 工程师 $G_0$ 在二进制文件 2 上工作以实现功能 foo。在这种情况下，$R_{B2} = 3$，因为二进制文件 2 中有三个服务（sb、sc 和 sd），且 $C_{B2} = 0$，因为那天没有其他工程师在该二进制文件上工作。总的来说，工程师需要 $D_{foo} + 3 + 0$ 天在二进制文件 2 上为功能 foo 工作。类似地，工程师 G1 需要 $D_{bar} + 1 + 0$，其中 1 是二进制文件 1 中的服务数量（服务 sa）。(b) 两名工程师都在二进制文件 2 上实现不同的功能。假设工程师 $G_0$ 首先在该二进制文件上开始，$G_0$ 需要 $D_{foo} + 3 + 0$ 天：因为没人在二进制文件 2 上工作，$C_{B2} = 0$。工程师 $G_1$ 需要 $D_{bar} + 3 + 1$ 天。(c) 两名工程师可以处理同一功能（此处为功能 bar），但前提是他们在两个不同的二进制文件中工作。(d) 不允许两名工程师在同一二进制文件上处理同一功能。 ##### 任务：移动一个服务 工程师可以将服务 $S_i$ 从一个二进制文件 $B_j$ 移动到**不同的**二进制文件 $B_k$。移动后，所有需要服务 $S_i$ 的功能将需要工程师在二进制文件 $B_k$ 上工作，而不是在 $B_j$ 上。已在服务 $S_i$ 中实现的功能仍然保持实现。 将服务 $S_i$ 从二进制文件 $B_j$ 移动到 $B_k$ 需要 $\max(R_{B_j}, R_{B_k})$ 天，其中 $R_{B_j}$ 和 $R_{B_k}$ 分别是移动前在二进制文件 $B_j$ 和 $B_k$ 中运行的服务数量。 :::align{center}  ::: 图 3. 工程师 $G_0$ 将服务 sc 从二进制文件 1 移动到二进制文件 2。注意这会影响两个功能（foo 和 bar）。 在移动完成之前，其他工程师不能开始在二进制文件 $B_j$ 和 $B_k$ 上工作，并且如果此时有任何工程师正在任一二进制文件上工作（实现功能或向/从这些二进制文件之一移动服务），则不能开始移动。 ##### 任务：创建一个新的二进制文件 工程师可以花费 $N$ 天创建一个新的空二进制文件。其 ID 是尚未使用的最小正整数。 :::align{center}  ::: 图 4. 工程师 $G_1$ 创建一个新的空二进制文件（二进制文件 3）。 ##### 任务：等待 工程师可以等待若干天。 :::align{center}  ::: 图 5. 一名工程师休息等待，例如观看哈基米视频。

输入数据 [完整输入（压缩）](https://www.luogu.com.cn/fe/api/problem/downloadAttachment/vi6horxa) #### 文件格式 每个输入数据集以纯文本文件提供。文件仅包含 ASCII 字符，行以单个 `\n` 字符（也称为“UNIX 风格”行结尾）结束。当一行中给出多个数字或字符串时，它们之间用单个空格分隔。 - 第一行： - 时间限制（天数） $L$ ($1 \leq L \leq 10^3$), - 谷歌工程师数量 $G$ ($1 \leq G \leq 10^5$), - 服务数量 $S$ ($1 \leq S \leq 10^4$), - 初始二进制文件数量 $B$ ($1 \leq B \leq 10^4$), - 功能数量 $F$ ($1 \leq F \leq 10^4$), - 创建新二进制文件所需的天数 $N$ ($1 \leq N \leq 10$). - 接下来的 $S$ 行描述服务，每行包含： - 服务名称（由 1-20 个小写字母 a-z 和连字符 - 组成的字符串）， - 一个整数 $B_i$ ($0 \leq B_i \leq B - 1$) - 服务最初运行的二进制文件的 ID。二进制文件编号从 0 到 $B - 1$。 - 接下来的 $F$ 块行描述功能。每个块： - 第一行包含： - 功能名称（由 1-20 个小写字母 a-z 和连字符 - 组成的字符串）， - $M_i$ ($1 \leq M_i \leq S$) - 需要修改以支持第 $i$ 个功能的服务数量， - $D_i$ ($1 \leq D_i \leq 10^2$) - 第 $i$ 个功能的难度， - $U_i$ ($1 \leq U_i \leq 10^5$) - 一旦该功能发布，将受益于它的每日用户数量。 - 第二行包含字符串列表 $S_{i,1}, S_{i,2}, ..., S_{i,M_i}$ - 需要修改以支持第 $i$ 个功能的服务名称。

你的提交描述工程师工作的调度。 #### 文件格式 - 第一行： $E$ - 我们为其计划工作的工程师数量 ($0 \leq E \leq G$) - 接下来的 $E$ 块： - 第一行： $T$ ($1 \leq T \leq L$) - 给定工程师的任务数量。 - 接下来的 $T$ 行包含以下之一： - 字面量 `impl` 后跟功能名称 $F_i$ 和一个数字 $B_j$ - 工程师应在 ID 为 $B_j$ 的二进制文件中实现名为 $F_i$ 的功能。 - 字面量 `move` 后跟服务名称 $S_i$ 和一个数字 $B_j$ - 工程师应将服务 $S_i$ 从二进制文件 $B_k$（服务 $S_i$ 在移动时所处的二进制文件）移动到不同的二进制文件 $B_j$。 - 字面量 `new` - 工程师应开始一个新的（空）二进制文件。 - 字面量 `wait` 后跟数字 $W$ ($1 \leq W \leq L$) - 工程师应等待 $W$ 天。

#### 示例 以下示例输入数据集与图 1 中所示的匹配。 | 输入文件 | 描述 | |:-:|:-:| | `10 2 5 3 2 5` | 10 天，2 名工程师，5 个服务，3 个二进制文件和 2 个功能，我们需要 5 天来创建一个新的二进制文件。 | | `sa 1` | 第一个服务名为 'sa'，在二进制文件 1 中运行 | | `sb 2` | 第二个服务名为 'sb'，在二进制文件 2 中运行 | | `sc 1` | 第三个服务名为 'sc'，在二进制文件 1 中运行 | | `sd 2` | 第四个服务名为 'sd'，在二进制文件 2 中运行 | | `se 0` | 第五个服务名为 'se'，在二进制文件 0 中运行 | | `foo 3 3 100` | foo 功能在 3 个服务中实现，其难度为 3，每天有 100 名用户受益 | | `sc sb sd` | foo 功能在服务 sc、sb 和 sd 中实现 | | `bar 2 1 20` | bar 功能在 2 个服务中实现，其难度为 1，每天有 20 名用户受益 | | `sc sa` | bar 功能在服务 sc 和 sa 中实现 | **注意，输入文件不包含任何空行。上例中的空行和换行是为了清晰而添加的。** | 提交文件 | 描述 | |:-:|:-:| | `2` | 两名工程师都将工作 | | `2` | 第一名工程师将执行 2 个任务 | | `move sc 2` | 将服务 sc 移动到二进制文件 2 | | `impl foo 2` | 在二进制文件 2 中实现功能 foo | | `3` | 第二名工程师将执行 3 个任务 | | `wait 2` | 等待 2 天 | | `impl bar 1` | 在二进制文件 1 中实现功能 bar | | `impl bar 2` | 在二进制文件 2 中实现功能 bar | :::align{center}  ::: 图 6. 工程师工作的时间线。对于工程师 $G_0$，将 cs 从其初始所在的二进制文件 1 移动到二进制文件 2 将需要 $\max(R_{B1}, R_{B2})$，即 2 天。在二进制文件 2 中实现 foo 将需要 6 天：$D_{foo} + R_{B2} + C_{B2}$，其中 $D_{foo} = 3$，$R_{B2} = 3$ 且 $C_{B2} = 0$。类似地，对于工程师 $G_1$，我们可以计算为实现 bar 功能在每个二进制文件上所需的天数。 :::align{center}   ::: 图 7. 每名工程师在每给定时间的工作：**(a)** 第 0 天到第 2 天之间，**(b)** 第 2 天到第 4 天之间，**(c)** 第 4 天到第 8 天之间。第 8 天后，功能 foo 上线，并一直保持到时间限制（第 10 天），因此为 2 天。功能 bar 在第 9 天后上线，因此保持 1 天。 #### 评分 工程师根据提交文件**一个接一个地立即**执行计划的任务。如果工程师被安排执行一项任务但无法执行（例如，他们无法移动服务，因为另一名工程师仍在同一二进制文件上工作），则该解决方案被视为无效，得 0 分。 工程师在时间限制之前完成任务是有效的。安排将在时间限制之后开始或完成的任务也是有效的（此类任务将被忽略）。 一旦一个功能在时间限制之前在其所有相关服务中实现，它立即发布，用户开始受益于它。只部分实现一个功能是有效的（例如，如果处理它的工程师将在时间限制之后完成，或者甚至没有在某些二进制文件中开始实现该功能），但它不会获得任何分数。同样，在时间限制之后完全实现的功能是允许的，但不会获得任何分数。 每个在时间限制之前发布的功能获得的分数等于 $U_i \times \max(0, L - I_i)$ 其中 - $U_i$ - 受益于第 $i$ 个功能的用户数量 - $L$ - 时间限制（天数） - $I_i$ - 第 $i$ 个功能发布的日期（完全实现第 $i$ 个功能所需的天数）。 总得分是每个发布功能所获分数的总和。 #### 示例 例如，在上面的示例中，第一名工程师将花费两天时间将服务 $sc$ 从二进制文件 1 移动到二进制文件 2：最初二进制文件 1 中有 2 个服务，二进制文件 2 中有 2 个服务，所以 $\max(2, 2) = 2$。然后第一名工程师将花费 6 天（$3 + 3 + 0$）在那里实现功能 foo。所以 foo 将在第 8 天准备就绪，意味着它将上线两天（直到第 10 天，即时间限制），获得 200（$= 2 \text{ 天} \times 100 \text{ 用户}$）分。 第二名工程师将等待 2 天，然后花费 2 天（$1 + 1 + 0$）在二进制文件 1 中实现功能 bar。然后他们将花费 5 天（$1 + 3 + 1$）在二进制文件 2 中实现功能 bar。该功能将上线 1 天，获得 20 分。 最终得分为 **220** ($200 + 20$) 分。 **注意，有多个数据集代表问题的单独实例。你团队的最终得分将是各个数据集上最佳得分的总和。** 你需要在本题中获得总共不低于 270000000 分，才可以被视作通过本题。赛场上的最高分是 370364455 分。 翻译由 DeepSeek 完成