P15270 [Google Hashcode 2022 Qualification] Mentorship and Teamwork

当我们成为团队的一部分时，工作会变得更有趣！通过结合我们不同的技能，我们可以更有创造力、更高效、更富有成效。更重要的是，当我们一起工作时，我们分享……不仅仅是披萨，还有知识。我们可以互相学习，提高自己的技能并积累经验。 团队合作是 Hash Code 的主要成分之一，尤其是在这个挑战中！ 那么，你准备好接受挑战了吗？ ### 摘要 你被给予一份贡献者列表，他们已掌握各种技能，以及一份具有不同技能要求的项目列表。贡献者可以通过完成项目来提高技能，并且可以互相指导，以担任他们原本无法胜任的角色。你的任务是将贡献者分配到适合他们资格的项目角色中，并最大化完成项目的得分。

#### 贡献者 有 $N$ 个贡献者。每个贡献者有一个名字和一个或多个特定水平的技能（$0, 1, 2, \dots$）。不拥有某项技能相当于拥有水平 $0$ 的该技能。 ::::info[例如：] 例如，三个贡献者可能拥有以下技能： - Anna：Python 水平 $3$ - Bob：C++ 水平 $3$ - Maria：HTML 水平 $4$，CSS 水平 $6$ :::align{center}  ::: :::: #### 项目 有 $M$ 个项目。每个项目描述如下： - 其名称 - 项目持续时间（以天为单位）——一旦开始，完成项目所需的天数 - 完成项目奖励的得分 - “最佳截止”时间（以天为单位）——如果项目工作的最后一天严格在指定日期之前，则获得满分。如果延迟（即项目在“最佳截止日”当天或之后仍在进行），则每延迟一天扣除一分，但得分不低于零分。另请参阅下方“分配”部分中的示例。 - 项目工作所需的贡献者角色列表 每个项目有一个或多个需要贡献者担任的角色。每个角色需要一项特定水平的技能，并且由单个贡献者担任。每个贡献者在单个项目中最多担任**一个角色**。 ::::info[例如：] 例如，一个名为 "WebServer" 的项目可能具有以下角色： - 角色 0 需要 Python 水平 $3$ - 角色 1 需要 HTML 水平 $1$ - 角色 2 需要 CSS 水平 $5$ :::align{center}  ::: :::: #### 担任角色与指导 贡献者可以被分配到项目中担任特定角色（在单个项目中最多一个角色），如果他们满足以下条件之一： - 拥有所需水平或更高的技能；或者 - 拥有恰好比所需水平低一级的技能，**仅当同一项目中的另一位贡献者（担任另一个角色）拥有该技能所需水平或更高时。** 在这种情况下，该贡献者将由他们的同事指导 :) 一位贡献者可以同时指导多个人，包括针对同一技能。一位贡献者可以同时指导其他贡献者和被其他贡献者指导。 不拥有某项技能相当于拥有水平 $0$ 的该技能。因此，如果贡献者不懂任何 C++，他们可以在一个需要 C++ 水平 $1$ 的角色上工作，前提是团队中有人**知道 C++ 水平 $1$ 或更高。** ::::info[例如：] 对于上述 WebServer 项目，我们可以进行以下分配： 角色 0（需要 Python 水平 $3$）分配给 Anna（Python 水平 $3$）。 ✅ Anna 的 Python 水平与所需水平相同。 角色 1（需要 HTML 水平 $1$）分配给 Bob（C++ 水平 $3$）。 ⚠️ Bob 的 HTML 水平为 $0$。由于他的水平仅比所需低一级，他可以被分配，但必须由另一位知道 HTML 水平 $1$ 或以上的贡献者指导。 角色 2（需要 CSS 水平 $5$）分配给 Maria（HTML 水平 $4$，CSS 水平 $6$） ✅ Maria 的 CSS 水平高于所需水平。 ✅ Maria 可以指导 Bob 的 HTML，因为她有 HTML 水平 $4$。 :::: #### 分配 每个贡献者可以从第 $0$ 天开始工作，并且同一时间最多只能在一个项目上工作。一旦项目工作开始，其贡献者将工作天数等于其持续时间，然后变得可用于其他项目。 :::info[例如：] 例如，如果项目 WebServer 的持续时间为 $7$ 天并从第 $0$ 天开始，则分配给的贡献者将在以下时间工作：第 $0$ 天、第 $1$ 天、第 $2$ 天、第 $3$ 天、第 $4$ 天、第 $5$ 天和第 $6$ 天。在第 $7$ 天，项目已经完成。分配给的贡献者可以在第 $7$ 天开始另一个项目。 ::: #### 学习 完成项目是一个学习机会，尤其是对于那些在现有能力边缘工作的贡献者！当每个项目完成时： - 在所需技能水平等于或高于其当前水平的角色中工作的贡献者将其技能水平提高一级 - 其他贡献者保持其技能水平 注意，**指导**他人不会提高指导者的技能水平。 :::info[例如：] 在上述分配中： - Anna 将 Python 技能提高到水平 $4$； - Bob 将 HTML 技能提高到水平 $1$； - Maria 既没有提高 CSS 技能（因为 Maria 的 CSS 水平已经高于所需），也没有提高 HTML 技能（因为她的角色需要 CSS，而不是 HTML）。 :::

[输入数据 完整输入（压缩）](https://www.luogu.com.cn/fe/api/problem/downloadAttachment/3g6taw24) 每个输入数据集以纯文本文件提供。文件仅包含 ASCII 字符，行以单个 `\n` 字符（也称为“UNIX 风格”行结尾）结束。当一行中给出多个字符串和数字时，它们之间用单个空格分隔。 数据集的第一行包含： - 一个整数 $C$ ($1 \leq C \leq 10^5$) —— 贡献者数量， - 一个整数 $P$ ($1 \leq P \leq 10^5$) —— 项目数量。 接下来是 $C$ 个部分，描述各个贡献者。每个贡献者由以下行描述： - 第一行包含： - 贡献者的名称（最多 20 个字符的 ASCII 字符串，所有字符均为小写或大写英文字母 a-z 和 A-Z，或数字 0-9）， - 一个整数 $N$ ($1 \leq N \leq 100$) —— 贡献者的技能数量。 - 接下来的 $N$ 行描述贡献者的各个技能。每行包含： - 技能名称（最多 20 个字符的 ASCII 字符串，所有字符均为小写或大写英文字母 a-z 和 A-Z、数字 0-9、短横线 '-' 或加号 '+'）， - 一个整数 $L_i$ ($1 \leq L_i \leq 10$) —— 技能水平。 接下来是 $P$ 个部分，描述各个项目。每个项目由以下行描述： - 第一行包含： - 项目名称（最多 20 个字符的 ASCII 字符串，所有字符均为小写或大写英文字母 a-z 和 A-Z 或数字 0-9）， - 一个整数 $D_i$ ($1 \leq D_i \leq 10^5$) —— 完成项目所需的天数， - 一个整数 $S_i$ ($1 \leq S_i \leq 10^5$) —— 项目完成奖励的得分， - 一个整数 $B_i$ ($1 \leq B_i \leq 10^5$) —— 项目的“最佳截止”日， - 一个整数 $R_i$ ($1 \leq R_i \leq 100$) —— 项目中的角色数量。 - 接下来的 $R_i$ 行描述项目中的技能： - 一个字符串 $X_k$ —— 技能名称（最多 20 个字符的 ASCII 字符串，所有字符均为小写或大写英文字母 a-z 和 A-Z、数字 0-9、短横线 '-' 或加号 '+'）， - 一个整数 $L_k$ ($1 \leq L_k \leq 100$) —— 所需技能水平。

提交文件应为仅包含 ASCII 字符的纯文本文件。 #### 文件格式 你的提交描述每个贡献者将参与哪些项目以及担任什么角色。 第一行应包含整数 $E$ ($0 \leq E \leq P$) —— 执行的项目数量。 接下来是 $E$ 个部分，每个部分描述一个完成的项目。每个项目由两行描述： - 一行包含项目名称（与输入文件中出现的相同）。每个项目在提交文件中最多被提及一次。 - 一行包含分配给每个项目角色的贡献者名称，以单个空格分隔，并按照与输入文件中角色出现的相同顺序列出。

#### 示例 | 输入文件 | 描述 | |:-:|:-:| | `3 3` | 3 个贡献者，3 个项目 | | `Anna 1` | 贡献者 Anna | | `C++ 2` | 拥有 C++ 技能水平 $2$ | | `Bob 2` | 贡献者 Bob | | `HTML 5` | 拥有 HTML 技能水平 $5$ | | `CSS 5` | 拥有 CSS 技能水平 $5$ | | `Maria 1` | 贡献者 Maria | | `Python 3` | 拥有 Python 技能水平 $3$ | | `Logging 5 10 5 1` | 项目 Logging 需要 1 位贡献者 | | `C++ 3` | 需要拥有 C++ 水平 $\geq 3$（在指导下可为 $2$） | | `WebServer 7 10 7 2` | 项目 WebServer 需要 2 位贡献者 | | `HTML 3` | 第一位贡献者需要拥有 HTML 水平 $\geq 3$（在指导下可为 $2$） | | `C++ 2` | 第二位贡献者需要拥有 C++ 水平 $\geq 2$（在指导下可为 $1$） | | `WebChat 10 20 20 2` | 项目 WebChat 需要 2 位贡献者 | | `Python 3` | 第一位贡献者需要拥有 Python 水平 $\geq 3$（在指导下可为 $2$） | | `HTML 3` | 第二位贡献者需要拥有 HTML 水平 $\geq 3$（在指导下可为 $2$） | :::align{center}   ::: | 提交文件 | 描述 | |:-:|:-:| | `3` | 计划了三个项目 | | `WebServer` | 项目 WebServer 的分配 | | `Bob Anna` | Bob → 第一个角色，Anna → 第二个角色 | | `Logging` | 项目 Logging 的分配 | | `Anna` | Anna → 第一个角色 | | `WebChat` | 项目 WebChat 的分配 | | `Maria Bob` | Maria → 第一个角色，Bob → 第二个角色 | #### 评分 每个贡献者同一时间只能在一个项目上工作。如果一个贡献者被分配到多个项目，他们将按照提交文件中出现的顺序工作。每个项目在所有分配的贡献者都空闲的第一天立即开始。 :::align{center}  ::: 如果某些项目分配无效，因为分配的贡献者在完成所有先前分配的项目后没有达到项目所需的技能水平，则提交视为无效，不会得分。 每个成功完成的项目根据输入文件中的定义获得其分配的得分，减去延迟的罚分。如果项目在“最佳截止”时间之后完成，则每延迟一天扣除一分（但得分不低于零分）。请注意，即使项目得分为零，分配的贡献者仍将工作（并可能因此提高技能）。 总得分为所有正确完成项目的得分之和。 :::info[示例提交导致以下时间线：] **第 0 天到第 6 天**：Bob 和 Anna 正在项目 **WebServer** 上工作（他们都拥有所需技能）。 - 项目完成时，Anna 的 C++ 水平提升：水平 $2 \rightarrow 3$； - Bob 没有提升，因为他的 HTML 技能（水平 $5$）高于项目所需水平（水平 $3$）。 项目 WebServer 工作的最后一天是第 $6$ 天，因此它在“最佳截止”日第 $7$ 天之前完成，获得满分：**10 分**。 **第 7 天到第 11 天**：Anna 正在项目 **Logging** 上工作（在完成项目 WebServer 后，她拥有足够的 C++ 技能）。 - 项目完成时，Anna 的 C++ 水平提升：水平 $3 \rightarrow 4$； 项目 Logging 工作的最后一天是第 $11$ 天（因此它在第 $12$ 天之前完成），而它的“最佳截止”日是第 $5$ 天。它延迟了 $(12 - 5 =) 7$ 天，获得得分：$(10 - 7 =) 3$ 分。 **第 7 天到第 16 天**：Maria 和 Bob 正在项目 **WebChat** 上工作 - 项目完成时，Maria 的 Python 水平提升：水平 $3 \rightarrow 4$； - Bob 的 HTML 没有提升，因为他的技能水平高于项目所需（HTML 水平 $5$，所需 $3$） 项目 WebChat 工作的最后一天是第 $16$ 天，而“最佳截止”日是第 $20$ 天，因此它获得满分：**20 分**。 最终，项目 WebServer（**10 分**）、Logging（**3 分**）和 WebChat（**20 分**）完成，总得分为 **33 分**。 ::: **注意，有多个数据集代表问题的单独实例。你团队的最终得分将是各个数据集最佳得分的总和。** 你需要在本题中获得总共不低于 3500000 分，才可以被视作通过本题。赛场上的最高分是 4220236 分。 翻译由 DeepSeek 完成