内容
问题概述
这个问题是最大限度地利用现有的机械和人员(简称“工人”)进行农业设备共享服务,接受农业工作(简称“工作”),同时最大化奖励*。您最初将从分布在空间上的许多作业中选择要接受的作业,然后生成和更新作业绩效计划,向工人输出处理作业的指令。每个作业由多个需要指定处理量的“任务”组成,当工作人员处理完这些“任务”时,就被认为完成了。基本上所有接受的工作都必须完成(否则将对未完成的工作进行处罚)。奖励是通过完成工作获得的,但奖励的多少取决于任务完成的时间,因此必须考虑处理每项任务的适当时间范围。特定时间可以处理的任务数量还取决于工人的能力和天气。提供指定时间段的天气预报。
*奖励:假设农作物的收获时间和农业设备的可再生能源供应率等因素。
以下数据作为初始输入给出。
- 工作时间范围
- 地理数据(图表)
- 工人数据
- 所有作业数据
- 天气相关数据
- 时间表相关数据
给定此数据,您应输出:
- 您将接受哪些工作。
然后,在每个时间点开始时,将提供以下数据作为输入:
- 有关已接受作业的数据。
- 工人的当前位置。
- 天气预报(设定的时间间隔)。
根据此数据,您必须输出:
- 工作绩效时间表
- 每个工人的操作
重复此循环,直到指定的工作时间范围结束。
您的输出将根据以下因素进行评分:
- 获得的奖励。
- 未完成作业的处罚。
- 时间表的遵循和更改程度。
下面给出更详细的描述。
输入 1
初始输入为:
- 工作时间范围
- 地理数据(图)
- 工人数据
- 所有作业数据
- 天气相关数据
- 时间表相关数据
该数据在标准输入上以以下格式给出:
T_{\rm{max}}\\
N_V\,\,N_E\\
u_1\quad v_1\quad d_1\\
\vdots\\
u_{N_E}\,\, v_{N_E}\,\, d_{N_E}\\
N_{\rm{worker}}\\
v^{\rm{init}}_1\,\,L^\text{max}_1\,\,N^{\rm{JobType}}_1\,\,\text{Type}^1_1\,\,\text{Type}^1_2\,\,\cdots \text{Type}^1_{N^{\rm{JobType}}_1}\\
\vdots\\
v^{\rm{init}}_{N_{\rm{worker}}}\,\,L^\text{max}_{N_{\rm{worker}}}\,\,N^{\rm{JobType}}_{N_{\rm{worker}}}\,\,\text{Type}^{N_{\rm{worker}}}_1\,\,\text{Type}^{N_{\rm{worker}}}_2\,\,\cdots \text{Type}^{N_{\rm{worker}}}_{N^{\rm{JobType}}_1}\\
N_{\rm{job}}\\
\text{Job}_1\\
\vdots\\
\text{Job}_{N_{\rm{job}}}\\
T^{\rm{weather}}\,\,N^{\rm{weather}}\\
\begin{array}{llll}
p^{\rm{weather}}_{1,1} & p^{\rm{weather}}_{1,2} & \cdots & p^{\rm{weather}}_{1,N^{\rm{weather}}}\\
p^{\rm{weather}}_{2,1} & p^{\rm{weather}}_{2,2} & \cdots & p^{\rm{weather}}_{2,N^{\rm{weather}}}\\
\vdots & \vdots & \ddots & \vdots\\
p^{\rm{weather}}_{N^{\rm{weather}},1} & p^{\rm{weather}}_{N^{\rm{weather}},2} & \cdots & p^{\rm{weather}}_{N^{\rm{weather}},N^{\rm{weather}}}\\
\end{array}\\
c_1\,\,c_2\,\,\cdots\,\,c_{N^{\rm{weather}}}\\
P_m\,\, R_m\,\, \alpha\\
t_1\,\, p^1_1\,\, p^1_2\,\, \cdots \,\, p^1_{N^{\rm{weather}}}\\
t_2\,\, p^2_1\,\, p^2_2\,\, \cdots \,\, p^2_{N^{\rm{weather}}}\\
\vdots\\
t_{N'}\,\, p^{N'}_1\,\, p^{N'}_2\,\, \cdots \,\, p^{N'}_{N^{\rm{weather}}}
工作时间范围
- 输入
- 工作时间范围的长度,T_\text{max},在第一行给出。
对于这个问题,时间值, t,将为整数值 1 to T_{\text{max}}.
输入示例
以下是一个示例 T_\text{max}=300
300
(该行以换行符结束)
地理数据
- 输入
- 下一行给出顶点数, N_V和边缘, N_E,用于表示问题的地理数据的图(具有正权重的连通无向图)。
- 的 N_V 各个顶点的编号将从 1 to N_V.
- 以下 N_E 行给出每条边的数据:顶点 u_i,v_i和重量 d_i (距离)。请注意 1\leq i \leq N_E.
- 下一行给出顶点数, N_V和边缘, N_E,用于表示问题的地理数据的图(具有正权重的连通无向图)。
如下所述, 职位 位于顶点并且 工人 沿着该图的边缘移动。
输入示例
以下是一个示例 N_V=14,N_E=19:
14 19 1 7 1 1 2 1 2 9 1 2 3 1 3 5 1 3 7 1 3 6 1 4 13 2 4 10 2 4 6 1 4 5 1 6 8 1 7 8 1 8 14 2 9 11 2 10 12 2 10 11 2 12 13 2 13 14 2
(最后一行以换行符结束)
- 第 1 行:该图有
14顶点和19边缘(N_V=14,N_E=19).- 顶点索引来自 1 to
14分配给这些14顶点。 - 下面,顶点索引对应的顶点 i 将简称为顶点 i.
- 顶点索引来自 1 to
- 第 2 行:有一个长度为边的边
1顶点之间1和7(u_{1}=1,v_{1}=7,d_{1}=1). - 第 3 行:有一个长度为边的边
1顶点之间1和2(u_{2}=1,v_{2}=2,d_{2}=1). - 第 4 行:有一个长度为边的边
1顶点之间2和9(u_{3}=2,v_{3}=9,d_{3}=1). - 第5行:有一条长度为边的边
1顶点之间2和3(u_{4}=2,v_{4}=3,d_{4}=1). - 第6行:有一个长度为边的边
1顶点之间3和5(u_{5}=3,v_{5}=5,d_{5}=1). - 第7行:有一个长度为边的边
1顶点之间3和7(u_{6}=3,v_{6}=7,d_{6}=1). - 第8行:有一个长度为边的边
1顶点之间3和6(u_{7}=3,v_{7}=6,d_{7}=1). - 第9行:有一个长度为边的边
2顶点之间4和13(u_{8}=4,v_{8}=13,d_{8}=2). - 第10行:有一个长度为边的边
2顶点之间4和10(u_{9}=4,v_{9}=10,d_{9}=2). - 第11行:有一个长度为边的边
1顶点之间4和6(u_{10}=4,v_{10}=6,d_{10}=1). - 第12行:有一个长度为边的边
1顶点之间4和5(u_{11}=4,v_{11}=5,d_{11}=1). - 第13行:有一个长度为边的边
1顶点之间6和8(u_{12}=6,v_{12}=8,d_{12}=1). - 第14行:有一个长度为边的边
1顶点之间7和8(u_{13}=7,v_{13}=8,d_{13}=1). - 第15行:有一个长度为边的边
2顶点之间8和14(u_{14}=8,v_{14}=14,d_{14}=2). - 第16行:有一个长度为边的边
2顶点之间9和11(u_{15}=9,v_{15}=11,d_{15}=2). - 第17行:有一个长度为边的边
2顶点之间10和12(u_{16}=10,v_{16}=12,d_{16}=2). - 第18行:有一个长度为边的边
2顶点之间10和11(u_{17}=10,v_{17}=11,d_{17}=2). - 第19行:有一个长度为边的边
2顶点之间12和13(u_{18}=12,v_{18}=13,d_{18}=2). - 第 20 行(=1+N_E): 有一条长度为边的边
2顶点之间13和14(u_{19}=13,v_{19}=14,d_{19}=2).
工人
工作人员是处理作业的实体,具有移动和执行任务的能力。他们根据参赛者的输入进行操作(参见 工人行动).
- 输入
- 工人数量, N_{\text{worker}},在下一行给出。
接下来是 N_{\text{worker}} 行包含工作配置数据:
- 初始位置(顶点索引): v^{\text{init}}_i
- 工人每单位时间可以执行的最大任务数: L^{\text{max}}_i
- 工人可以执行的工作类型数量, N^{\text{JobType}}_i ,以及作业类型列表: \text{Type}^i_1\,\,\text{Type}^i_2\,\,\cdots\,\,\text{Type}^i_{N^{\text{JobType}}_i}
这些输入按工作人员 ID 的顺序给出。
每个工人每单位时间可执行的任务数量上限以及可完成的作业类型都不同。单位时间内实际可以完成的任务数量还取决于天气。
输入示例
以下是一个示例 N_{\text{worker}}=5:
5 6 100 3 1 2 3 13 59 1 3 10 55 2 2 3 9 47 3 1 2 3 9 89 1 2
(最后一行以换行符结束)
- 第 1 行:有
5工人(N_{\text{worker}}=5). - 第 2 行:ID=1 的工作人员的描述符。
- 工人的初始位置是具有顶点索引的顶点
6(v^{\text{init}}_1=6). - 该工作人员每单位时间可以执行的最大任务数为
100(L^{\text{max}}_1=100). - 工人可以执行
3工作类型(N^{\text{JobType}}_1=3),类型1,2,3(\text{Type}^1_1=1,\text{Type}^1_2=2,\text{Type}^1_3=3).
- 工人的初始位置是具有顶点索引的顶点
- 第 3 行:ID=2 的工作人员的描述符。
- 工人的初始位置是具有顶点索引的顶点
13(v^{\text{init}}_2=13). - 该工作人员每单位时间可以执行的最大任务数为
59(L^{\text{max}}_2=59). - 工人可以执行
1工作类型(N^{\text{JobType}}_2=1),类型3(\text{Type}^2_1=3).
- 工人的初始位置是具有顶点索引的顶点
- 第 4 行:ID=3 的工作人员的描述符。
- 工人的初始位置是具有顶点索引的顶点
10(v^{\text{init}}_3=10). - 该工作人员每单位时间可以执行的最大任务数为
55(L^{\text{max}}_3=55). - 工人可以执行
2工作类型(N^{\text{JobType}}_3=2),类型2,3(\text{Type}^3_1=2,\text{Type}^3_2=3).
- 工人的初始位置是具有顶点索引的顶点
- 第5行:ID=4的worker的描述符。
- 工人的初始位置是具有顶点索引的顶点
9(v^{\text{init}}_4=9). - 该工作人员每单位时间可以执行的最大任务数为
47(L^{\text{max}}_4=47). - 工人可以执行
3工作类型(N^{\text{JobType}}_4=3),类型1,2,3(\text{Type}^4_1=1,\text{Type}^4_2=2,\text{Type}^4_3=3).
- 工人的初始位置是具有顶点索引的顶点
- 第 6 行(=1+N_{\text{worker}}): ID=5的worker的描述符。
职位
作业是工作人员在其中一个顶点执行的工作。
- 一份工作:
- 是现实世界中的一个工作单元,例如收获农作物或施用农业化学品。
- 由多个较小的工作任务组成。例如,采摘一块水果、收割指定区域的水稻或在指定区域喷洒化学品。构成工作的这些较小量的工作将被称为“任务”。
- 通过完成构成作业的设定数量的任务来完成作业。
- 实际上,一项工作可能包含多种类型的任务,但在这种情况下,我们只关注任务的数量。因此, 只需处理一定数量的任务即可完成作业.
- 每个作业的作业位置都不同。对于这个问题, 这通过将每个作业定位在 地理数据 图 给出了问题。
- 任务处理及奖励
- 每个作业的任务由 工人.
- 参赛者应为每个工人输出指令 移动 和 执行工作,将它们移动到作业的顶点并执行作业的任务。
- 参赛者将获得奖励 完成作业(处理设定数量的任务).
- 每个工作人员每单位时间可以处理的任务数量都有上限(执行任务的限制),因此完成一项工作需要一定的时间。通常,在从设定时间起的每个设定时间间隔期间处理设定数量的任务。
- 完成工作时获得的奖励金额将取决于任务处理的时间。更具体地说,它是所有时间间隔的总和(t=1,2,\cdots,T_\text{max}), 的
该时间点处理的每个任务的奖励率的乘积 r(t) \times 该时间点处理的任务数量
- 奖励率, r(t) 用于处理每个时间点的任务 每个工作都不同.
- 所有工人收集的总奖励将是该问题得分的主要组成部分(评分方法)。参赛者需要决定工人的行动以最大化总奖励,同时还要考虑其他因素。
- 作业之间的依赖关系
- 某些作业依赖于其他作业。也就是说,如果一个作业依赖于另一个作业,则在另一个作业的任务完成之前,无法处理其任务。
- 如果一个作业不依赖于另一个作业,则不存在此类限制。
- 接受工作
- 参赛者必须 选择问题开头接受的作业 (输出 1).
- 有些工作是强制性的,因此所选作业必须包括所有强制作业。
- 如果在工作时间范围结束时未完成所有选定的作业,则会出现 未完成工作惩罚 指定每个作业 将产生 将会产生.
各种限制
- 输入
- 下一行给出 N_{\text{job}},作业数量。
- 接下来是指示每个作业的组成的行, \text{Job}_i,对于 N_{\text{job}} 工作(N_{\text{job}}\times 3 行)。
的组成 \text{Job}_i 按以下格式给出:
\text{ID}^{\rm{job}}_i\,\,\text{Type}_i\,\,N^{\rm{task}}_i\,\,v^{\rm{job}}_i\,\, P^{\rm{job}}_i\,\,d^\text{weather}_i\,\, f^{\rm{mandatory}}_i\\
N^{\rm{reward}}_i\,\, t^{\rm{reward}}_{i,1}\,\, y^{\rm{reward}}_{i,1}\cdots t^{\rm{reward}}_{i,N^{\rm{reward}}_i}\,\, y^{\rm{reward}}_{i,N^{\rm{reward}}_i}\\
N^{\rm{depend}}_i\,\, {\rm{id}}^{\rm{depend}}_{i,1}\,\, \cdots \,\,{\rm{id}}^{\rm{depend}}_{i,N^{\rm{depend}}_i}
- 第 1 行
- 作业 ID: \text{ID}^{\text{job}}_i
- 工作类型: \text{Type}_i
- 要完成的任务数量: N^{\text{task}}_i
- 作业位置(顶点索引): v^{\text{job}}_i
- 已接受但未完成的工作的惩罚系数: P^{\text{job}}_i
- 取决于天气: d^\text{weather}_i
- 强制作业标志: f^{\text{mandatory}}_i (0:可选, 1:强制)
- 第2行(奖励函数的定义, r(t))
- 奖励函数中控制点的数量:N^{\text{reward}}_i
- 控制点列表:t^{\rm{reward}}_{i,1}\,\,y^{\rm{reward}}_{i,1}\,\,t^{\rm{reward}}_{i,2}\,\,y^{\rm{reward}}_{i,2}\,\,\cdots\,\,t^{\rm{reward}}_{i,N^{\text{reward}}_i}\,\,y^{\rm{reward}}_{i,N^{\text{reward}}_i}
- 第 3 行(作业依赖性)
- 作业依赖项数量: N^{\text{depend}}_i
- 依赖作业 ID: {\rm{id}}^{\rm{depend}}_{i,1}\,\,{\rm{id}}^{\rm{depend}}_{i,2}\,\, \cdots \,\,{\rm{id}}^{\rm{depend}}_{i,N^{\rm{depend}}_i}
奖励功能 r(t) 详情
当时每个任务的奖励 t 功能 r(t) 由一个或多个控制点(时间和值对)以及这些点之间的线性插值来定义。
换句话说,给定控制点列表, p=((t_i,y_i))_{i=1,\cdots,n} (t_i,y_i\in \mathbb{Z},t_1 < t_2 < \cdots < t_n,n\geq 1),当时每个任务的奖励 t 功能 r(t) (实际上 r(t;p)),定义为:
r(t)=\begin{cases} y_1, & \text{if}\,\, t < t_1, \\ y_n, & \text{if}\,\, t \geq t_n, \\ (y_\text{next}-y_\text{prev})(t-t_\text{prev})/(t_\text{next}-t_\text{prev})+y_\text{prev}, & \text{otherwise}. \end{cases}
在这里, (t_\text{prev},y_\text{prev}) 是时间最长不超过的对 t,和 (t_\text{next},y_\text{next}) 是时间超过的最小对 t.
r(t),整数倍 r(t) 及其总和以小数计算。
输入示例
以下是一个示例 N_{\text{job}}=6 (请注意,这是极少数的作业):
6 1 1 906 10 0.94469412898840599 0.07857326752336613 0 13 11 0 12 1212810 37 1849941 63 2266874 88 1944271 113 1207029 139 768959 164 808665 189 992126 214 1137116 240 907954 265 903397 266 0 0 2 3 905 2 0.96478158647239831 0.056877102556647817 0 7 92 0 93 1280499 121 1553205 149 1429506 176 1419189 204 1731967 205 0 0 3 1 1052 4 0.94436951517275258 0.071240847781028308 0 7 191 0 192 1914094 218 1735762 244 1444725 270 1275768 296 975408 297 0 0 4 3 653 4 0.95274950239675604 0.14137003825803521 0 10 70 0 71 1319303 94 1329844 118 1503315 141 1161131 165 1294526 188 849137 212 1953166 235 2087503 236 0 1 2 5 1 1452 12 0.95747093286627682 0.076042573628832266 0 8 122 0 123 1667665 149 911519 174 1511934 200 1967913 225 1633211 251 1589845 252 0 2 6 4 6 2 737 6 0.95812926774107732 0.049371044631834608 1 11 82 0 83 1431723 108 1475010 133 1032345 158 1012865 183 1593586 207 1923638 232 1956884 257 2797127 282 2877123 283 0 0
- 第 1 行:作业总数为
6. (N_{\text{job}}=6)- 给出的实际问题将包括数百个作业。
- 第 2 行:ID=1 的作业描述开始。
- 作业 ID 是
1(\text{ID}^{\text{job}}_1=1). - 作业类型是
1(\text{Type}_1=1). - 完成此作业所需的任务数为
906(N^{\text{task}}_1=906). - 作业位于顶点
10(v^{\text{job}}_1=10). - 如果该作业被接受,但在工作时间范围结束时尚未完成(T_\text{max}),未完成的工作惩罚为
0.94469412898840599将被应用(评分方法) (P^{\text{job}}_1=0.94469412898840599). - 这项工作对天气的依赖性是
0.07857326752336613(执行任务的限制) (d^\text{weather}_1=0.07857326752336613). - 这项工作不是强制性的(f^{\text{mandatory}}_1=0).
- 作业 ID 是
- 第3行:ID=1的工作的奖励函数的定义。
- 有
13控制点(N^{\text{reward}}_1=13). - 控制点列表为:((
11,0), (12,1212810), (37,1849941), (63,2266874), (88,1944271), (113,1207029), (139,768959), (164,808665), (189,992126), (214,1137116), (240,907954), (265,903397), (266,0)).- 可获得奖励的次数为 12,13,\cdots,265.
- 有
- 第4行:ID=1的作业所依赖的作业。这样就完成了 ID=1 的作业的描述。
- 该作业所依赖的作业数量为
0(N^{\text{depend}}_1=0). - (因为它所依赖的作业数量是
0,没有给出作业 ID。)
- 该作业所依赖的作业数量为
- 第 5 行:ID=2 的作业描述开始。
- 作业 ID 是
2(\text{ID}^{\text{job}}_2=2). - 作业类型是
3(\text{Type}_2=3). - 完成此作业所需的任务数为
905(N^{\text{task}}_2=905). - 作业位于顶点
2(v^{\text{job}}_2=2). - 如果该作业被接受,但在工作时间范围结束时尚未完成(T_\text{max}),未完成的工作惩罚为
0.96478158647239831将被应用(评分方法) (P^{\text{job}}_2=0.96478158647239831). - 这项工作对天气的依赖性是
0.056877102556647817(执行任务的限制) (d^\text{weather}_2=0.056877102556647817). - 这项工作不是强制性的(f^{\text{mandatory}}_2=0).
- 作业 ID 是
- 第6行:ID=2的工作的奖励函数的定义。
- 有
7控制点(N^{\text{reward}}_2=7). - 控制点列表为:((
92,0), (93,1280499), (121,1553205), (149,1429506), (176,1419189), (204,1731967), (205,0)).- 可获得奖励的次数为 93,94,\cdots,204.
- 有
- 第7行:ID=2的作业所依赖的作业。这样就完成了 ID=2 的作业的描述。
- 该作业所依赖的作业数量为
0(N^{\text{depend}}_2=0). - (因为它所依赖的作业数量是
0,没有给出作业 ID。)
- 该作业所依赖的作业数量为
- 第 8 行:ID=3 的作业描述开始。
- 作业 ID 是
3(\text{ID}^{\text{job}}_3=3). - 作业类型是
1(\text{Type}_3=1). - 完成此作业所需的任务数为
1052(N^{\text{task}}_3=1052). - 作业位于顶点
4(v^{\text{job}}_3=4). - 如果该作业被接受,但在工作时间范围结束时尚未完成(T_\text{max}),未完成的工作惩罚为
0.94436951517275258将被应用(评分方法) (P^{\text{job}}_3=0.94436951517275258). - 这项工作对天气的依赖性是
0.071240847781028308(执行任务的限制) (d^\text{weather}_3=0.071240847781028308). - 这项工作不是强制性的(f^{\text{mandatory}}_3=0).
- 作业 ID 是
- 第9行:ID=3的工作的奖励函数的定义。
- 有
7控制点(N^{\text{reward}}_3=7). - 控制点列表为:((
191,0), (192,1914094), (218,1735762), (244,1444725), (270,1275768), (296,975408), (297,0)).- 可获得奖励的次数为 192,193,\cdots,296.
- 有
- 第10行:ID=3的作业所依赖的作业。这样就完成了 ID=3 的作业的描述。
- 该作业所依赖的作业数量为
0(N^{\text{depend}}_3=0). - (因为它所依赖的作业数量是
0,没有给出作业 ID。)
- 该作业所依赖的作业数量为
- 第 11 行:ID=4 的作业描述开始。
- 作业 ID 是
4(\text{ID}^{\text{job}}_4=4). - 作业类型是
3(\text{Type}_4=3). - 完成此作业所需的任务数为
653(N^{\text{task}}_4=653). - 作业位于顶点
4(v^{\text{job}}_4=4). - 如果该作业被接受,但在工作时间范围结束时尚未完成(T_\text{max}),未完成的工作惩罚为
0.95274950239675604将被应用(评分方法) (P^{\text{job}}_4=0.95274950239675604). - 这项工作对天气的依赖性是
0.14137003825803521(执行任务的限制) (d^\text{weather}_4=0.14137003825803521). - 这项工作不是强制性的(f^{\text{mandatory}}_4=0).
- 作业 ID 是
- 第12行:ID=4的工作的奖励函数的定义。
- 有
10控制点(N^{\text{reward}}_4=10). - 控制点列表为:((
70,0), (71,1319303), (94,1329844), (118,1503315), (141,1161131), (165,1294526), (188,849137), (212,1953166), (235,2087503), (236,0)).- 可获得奖励的次数为 71,72,\cdots,235.
- 有
- 第13行:ID=4的作业所依赖的作业。这样就完成了 ID=4 的作业的描述。
- 该作业所依赖的作业数量为
1(N^{\text{depend}}_4=1). - 该作业取决于 ID= 的作业
2(\text{id}^\text{depend}_{4,1}=2).
- 该作业所依赖的作业数量为
- 第 14 行:ID=5 的作业描述开始。
- 作业 ID 是
5(\text{ID}^{\text{job}}_5=5). - 作业类型是
1(\text{Type}_5=1). - 完成此作业所需的任务数为
1452(N^{\text{task}}_5=1452). - 作业位于顶点
12(v^{\text{job}}_5=12). - 如果该作业被接受,但在工作时间范围结束时尚未完成(T_\text{max}),未完成的工作惩罚为
0.95747093286627682将被应用(评分方法) (P^{\text{job}}_5=0.95747093286627682). - 这项工作对天气的依赖性是
0.076042573628832266(执行任务的限制) (d^\text{weather}_5=0.076042573628832266). - 这项工作不是强制性的(f^{\text{mandatory}}_5=0).
- 作业 ID 是
- 第15行:ID=5的工作的奖励函数的定义。
- 有
8控制点(N^{\text{reward}}_5=8). - 控制点列表为:((
122,0), (123,1667665), (149,911519), (174,1511934), (200,1967913), (225,1633211), (251,1589845), (252,0)).- 可获得奖励的次数为 123,124,\cdots,251.
- 有
- 第16行:ID=5的作业所依赖的作业。这样就完成了 ID=5 的作业的描述。
- 该作业所依赖的作业数量为
2(N^{\text{depend}}_5=2). - 该作业取决于 ID= 的作业
6,4(\text{id}^\text{depend}_{5,1}=6,\text{id}^\text{depend}_{5,2}=4).
- 该作业所依赖的作业数量为
- 第 17 行:ID=6 的作业描述开始。
- 作业 ID 是
6(\text{ID}^{\text{job}}_6=6). - 作业类型是
2(\text{Type}_6=2). - 完成此作业所需的任务数为
737(N^{\text{task}}_6=737). - 作业位于顶点
6(v^{\text{job}}_6=6). - 如果该作业被接受,但在工作时间范围结束时尚未完成(T_\text{max}),未完成的工作惩罚为
0.95812926774107732将被应用(评分方法) (P^{\text{job}}_6=0.95812926774107732). - 这项工作对天气的依赖性是
0.049371044631834608(执行任务的限制) (d^\text{weather}_6=0.049371044631834608). - 该工作是强制性的 (f^{\text{mandatory}}_6=1).
- 作业 ID 是
- 第18行:ID=6作业的奖励函数定义。
- 有
11控制点(N^{\text{reward}}_6=11). - 控制点列表为:((
82,0), (83,1431723), (108,1475010), (133,1032345), (158,1012865), (183,1593586), (207,1923638), (232,1956884), (257,2797127), (282,2877123), (283,0)).- 可获得奖励的次数为 83,84,\cdots,282.
- 有
- 第 19 行(=1+3\times N_{\text{job}}):ID=6 的作业所依赖的作业。这样就完成了 ID=6 的作业的描述。
- 该作业所依赖的作业数量为
0(N^{\text{depend}}_6=0). - (因为它所依赖的作业数量是
0,没有给出作业 ID。)
- 该作业所依赖的作业数量为
天气
天气是一个影响可以执行的任务数量的值,并且此状态在每个时间点都会发生概率变化。
- 输入
- 在下一行中,基本天气段的长度, T^\text{weather},以及天气状态的数量, 给出 N^\text{weather}。
- 在接下来的每个 N^\text{weather} 行,从状态转换的概率 i到其他州, 给出 p^{\text{weather}}_{i,1} \,\, p^{\text{weather}}_{i,2} \,\,\cdots \,\, p^{\text{weather}}_{i,N^{\text{weather}}}(转移概率矩阵)。
- 下一行给出常量, c_1\,\,c_2\,\,\cdots\,\,c_{N_\text{weather}},用于计算 执行任务的限制 每种天气状态。
对于此问题,该值固定为 N^\text{weather}=7 天气状态为:晴 (1)、大部分晴 (2)、小云 (3)、多云 (4)、小雨 (5)、中雨 (6) 和大雨 (7)
天气行为和更新
内部维护基本天气和实际天气状态,实际天气状态直接影响可以执行的任务数量。
基本天气
工作时间范围的总长度平均分为基本天气段, b_i (i=1,\cdots,n(=T_\text{max}/T^\text{weather})),长度 T^\text{weather}.
每个 b_i 具有独立的天气状态, w_i,称为基本天气状态。
在时间点 t=1,全部 w_i 是根据转移概率矩阵的平稳分布以概率方式独立确定的。 此后,每次 T^\text{weather} 时间流逝, 每个片段中的 w_i 根据转移概率矩阵独立更新。
实际天气状态
这里我们称之为实际天气状态 w. w 更新如下:
时间开始时 t,
- if t 等于天气片段的开始时间 b_i :w \leftarrow w_i (设置 w to w_i)
- 其他情况:更新 w 根据转移概率矩阵。
注意,基本天气状态的更新是在更新实际天气状态之前执行的。
当其他部分提到天气(值或状态)时,它指的是实际的天气状态, w.
对于每个测试用例,用于确定天气的种子值被赋予不同的值。
In 输入 2,每个天气状态的概率 T^\text{weather} 未来的间隔每次都给出 T^\text{weather} 已过去,开始时间 t=1 (包括此时的概率数据 t=1).
输入示例
以下是一个示例 T^\text{weather}=10 和 N^\text{weather}=7.
10 7 0.65038945819291316 0.3456395688250497 0.0039709729820371371 0 0 0 0 0.29367291714300126 0.57978625074387669 0.11253142456916906 0.014009407543952863 0 0 0 1.4131189430426344e-09 0.18905960051799561 0.44909739165434842 0.32239542530231813 0.039447581112218938 0 0 0 0.043752041690362654 0.079271361143687852 0.87011603340370036 0.0033077052290538069 0.0035528585331954204 0 0 0 0.015190350742277408 0.044334491311077411 0.90080171493640016 0.039640375730251982 3.3067279992976463e-05 0 0 0 2.9123680876183852e-09 0.21976983161374733 0.68711791872304939 0.093112246750835195 0 0 0 0 0.018677162951541051 0.41030647336908055 0.57101636367937847 0 1 2 3 10 14 20
- 第 1 行:基本天气段长度为
10,并且有7天气状态总计(T^\text{weather}=10,N^\text{weather}=7). - 第 2 行:状态的(基本)转移概率 1 说明 1,2,3,4,5,6,7 是:
0.65038945819291316,0.3456395688250497,0.0039709729820371371,0,0,0,0。 - 第 3 行:状态的(基本)转移概率 2 说明 1,2,3,4,5,6,7 是:
0.29367291714300126,0.57978625074387669,0.11253142456916906,0.014009407543952863,0,0,0。 - 第 4 行:状态的(基本)转移概率 3 说明 1,2,3,4,5,6,7 是:
1.4131189430426344e-09,0.18905960051799561,0.44909739165434842,0.32239542530231813,0.039447581112218938,0,0。 - 第 5 行:状态的(基本)转移概率 4 说明 1,2,3,4,5,6,7 是:
0,0.043752041690362654,0.079271361143687852,0.87011603340370036,0.0033077052290538069,0.0035528585331954204,0。 - 第 6 行:状态的(基本)转移概率 5 说明 1,2,3,4,5,6,7 是:
0,0,0.015190350742277408,0.044334491311077411,0.90080171493640016,0.039640375730251982,3.3067279992976463e-05。 - 第 7 行:状态的(基本)转移概率 6 说明 1,2,3,4,5,6,7 是:
0,0,0,2.9123680876183852e-09,0.21976983161374733,0.68711791872304939,0.093112246750835195。 - 第 8 行:状态的(基本)转移概率 7 说明 1,2,3,4,5,6,7 是:
0,0,0,0,0.018677162951541051,0.41030647336908055,0.57101636367937847。 - 第 9 行:状态的限制常数 1,2,3,4,5,6,7 是:
0,1,2,3,10,14,20。
时间表
参赛者必须为每个工人制定一份工作时间表(何时、哪项工作、多少),并根据时间表的表现获得额外积分。未按时完成的加分将会减少。时间表可以在执行过程中更改,但在接近时间的更改中获得的额外积分将减少更多。反之,以后的赛程改变得越远,增加的积分减少的就越少。
参见 输出 2 有关进度评估的详细信息。
如果不打算提交时间表,则可以提交任何时间表。
- 输入
- 下一行提供了最大的时间表更改惩罚 P_m,进度变更惩罚衰减率 R_m,以及日程附加积分系数 \alpha.
输入示例
0.029878077064496654 0.99054720249346828 0.87563809736779619
- 第 1 行:最大时间表更改惩罚为
0.029878077064496654,进度变更惩罚衰减率为0.99054720249346828,日程附加积分系数为0.87563809736779619.(P_m=0.029878077064496654,R_m=0.99054720249346828,\alpha=0.87563809736779619)
天气预报
为了决定接受哪些作业,在开始时间 (t=1)。结构相同 天气预报 输入 2 为 ,因此请参阅该部分了解详细信息。
完整输入 1 示例
300 14 19 1 7 1 1 2 1 2 9 1 2 3 1 3 5 1 3 7 1 3 6 1 4 13 2 4 10 2 4 6 1 4 5 1 6 8 1 7 8 1 8 14 2 9 11 2 10 12 2 10 11 2 12 13 2 13 14 2 5 6 100 3 1 2 3 13 59 1 3 10 55 2 2 3 9 47 3 1 2 3 9 89 1 2 6 1 1 906 10 0.94469412898840599 0.07857326752336613 0 13 11 0 12 1212810 37 1849941 63 2266874 88 1944271 113 1207029 139 768959 164 808665 189 992126 214 1137116 240 907954 265 903397 266 0 0 2 3 905 2 0.96478158647239831 0.056877102556647817 0 7 92 0 93 1280499 121 1553205 149 1429506 176 1419189 204 1731967 205 0 0 3 1 1052 4 0.94436951517275258 0.071240847781028308 0 7 191 0 192 1914094 218 1735762 244 1444725 270 1275768 296 975408 297 0 0 4 3 653 4 0.95274950239675604 0.14137003825803521 0 10 70 0 71 1319303 94 1329844 118 1503315 141 1161131 165 1294526 188 849137 212 1953166 235 2087503 236 0 1 2 5 1 1452 12 0.95747093286627682 0.076042573628832266 0 8 122 0 123 1667665 149 911519 174 1511934 200 1967913 225 1633211 251 1589845 252 0 2 6 4 6 2 737 6 0.95812926774107732 0.049371044631834608 1 11 82 0 83 1431723 108 1475010 133 1032345 158 1012865 183 1593586 207 1923638 232 1956884 257 2797127 282 2877123 283 0 0 10 7 0.65038945819291316 0.3456395688250497 0.0039709729820371371 0 0 0 0 0.29367291714300126 0.57978625074387669 0.11253142456916906 0.014009407543952863 0 0 0 1.4131189430426344e-09 0.18905960051799561 0.44909739165434842 0.32239542530231813 0.039447581112218938 0 0 0 0.043752041690362654 0.079271361143687852 0.87011603340370036 0.0033077052290538069 0.0035528585331954204 0 0 0 0.015190350742277408 0.044334491311077411 0.90080171493640016 0.039640375730251982 3.3067279992976463e-05 0 0 0 2.9123680876183852e-09 0.21976983161374733 0.68711791872304939 0.093112246750835195 0 0 0 0 0.018677162951541051 0.41030647336908055 0.57101636367937847 0 1 2 3 10 14 20 0.029878077064496654 0.99054720249346828 0.87563809736779619 1 0 0 0 0 1 0 0 11 0.32997661987364896 0.35720093880279286 0.10144180605929307 0.18397452127884667 0.023582674286464638 0.0033945272798704107 0.00042891241908338078 21 0.26146895868607978 0.29829553702903927 0.10367350846525671 0.27413103299772817 0.050432669277988201 0.010115966874572493 0.0018823266693354056 31 0.20903275687358913 0.2506351074109075 0.10197621041600768 0.32306215864825039 0.090561788952494518 0.020385340563280511 0.0043466371354700514 41 0.16453280991499084 0.20329129777873356 0.091390970778385427 0.30920472674724836 0.18000987309438846 0.041926491747270762 0.0096438299389825944 51 0.21773018584216544 0.25781470723187322 0.10129611879665416 0.30911960619088807 0.089756375035668315 0.020014729744938529 0.0042682771578124723 61 0.18695780159879197 0.22637031212950884 0.095692191594510659 0.30993166346993428 0.14119172380160475 0.032519854076175789 0.0073364533294737588 71 0.19978365794228928 0.23953773160128791 0.098109392505800377 0.31008680745444389 0.11925953673379487 0.027193693951331609 0.0060291798110520588 81 0.20381180897940113 0.24366400563862556 0.098856417213860404 0.3100620551039589 0.11244486750690874 0.02553797224640603 0.0056228733108393747 91 0.21098420754865557 0.2510068631469719 0.10018090439250056 0.30998380940692433 0.10034511870194431 0.02259771906125015 0.0049013777417531382 101 0.21017332149772244 0.25017760625955138 0.10003235653165234 0.30999988763169445 0.10170583135583394 0.022928465225827428 0.0049825314977181429 111 0.21035975914577648 0.25036818399930888 0.10006639945926016 0.30999551883837906 0.10139365148795368 0.02285257565351554 0.0049639114158061791 121 0.21006375850103443 0.25006523326156821 0.10001185087147714 0.3099994276865809 0.10189232028110375 0.022973761374232418 0.0049936480240032411 131 0.21003860874539299 0.25003947404099974 0.1000071910191422 0.30999960764692047 0.10193484214518268 0.022984093048729243 0.0049961833536327927 141 0.21002336947231043 0.25002386973415752 0.10000437307823702 0.30999975094869503 0.1019605735904045 0.022990345532450621 0.0049977176437451558 151 0.21001036314333912 0.25001055377029446 0.10000197057271488 0.30999988860662192 0.1019825193444605 0.022995678324735189 0.0049990262378340521 161 0.2098468891366603 0.24984320350327363 0.099971794472248382 0.31000174310451423 0.10225822676243579 0.023062676470061792 0.0050154665508059335 171 0.21001766063059757 0.25001802405322704 0.10000331731605842 0.30999980388842874 0.10197021368851594 0.022992687970461667 0.0049982924527108988 181 0.21000312608202204 0.25000314492830189 0.10000063442967058 0.30999996928440271 0.10199472644850339 0.022998644688091742 0.0049997541390076946 191 0.21000646152716931 0.25000655944481537 0.10000125010448897 0.30999993130167014 0.10198910119136487 0.022997277723427214 0.0049994187070641306 201 0.21000390597655963 0.25000394330415704 0.10000077837739391 0.30999996034571875 0.10199341120724155 0.022998325077383485 0.0049996757115455511 211 0.21000068372351638 0.25000064465305499 0.10000018358284854 0.30999999695861213 0.10199884564588058 0.022999645671209767 0.004999999764877615 221 0.21000123276535285 0.25000120671230119 0.10000028493014526 0.3099999907192631 0.10199791966912596 0.022999420654547454 0.0049999445492642201 231 0.2100001748189628 0.25000012368230085 0.10000008964391316 0.31000000273847578 0.10199970393318095 0.022999854238977081 0.0050000509441893055 241 0.21000051371752923 0.25000047061605735 0.10000015220117091 0.30999999888829144 0.10199913236874111 0.022999715346170929 0.0050000168620389848 251 0.21000030618472809 0.25000025816270716 0.10000011389270266 0.31000000124600918 0.10199948238020001 0.022999800400576097 0.0050000377330769279 261 0.2100000445095816 0.2499999902833088 0.1000000655900994 0.31000000421880708 0.10199992370466664 0.022999907644464797 0.0050000640490715734 271 0.21000008909654816 0.25000003592742104 0.10000007382040528 0.31000000371226893 0.10199984850715899 0.022999889371122236 0.0050000595650754173 281 0.21000000318197135 0.24999994797583083 0.10000005796143702 0.31000000468831079 0.10199999340515975 0.02299992458200726 0.005000068205283017 291 0.21000003070352388 0.24999997614991259 0.10000006304163929 0.31000000437564929 0.10199994698907894 0.022999913302684732 0.0050000654375114001
输出 1
收到此数据后,参赛者必须选择他们将接受的作业并产生以下格式的输出:
N^{\text{selected}}\,\, \text{id}_1\,\, \text{id}_2\,\,\cdots \,\,\text{id}_{N^{\text{selected}}}
(在最后一行后插入换行符)
接受工作
- 输出
- 第一行,输出接受的作业数量, N^{\text{selected}},以及已接受作业的 ID 列表, \text{id}_1\,\, \text{id}_2\,\,\cdots \,\,\text{id}_{N^{\text{selected}}}.
不满足以下条件将导致 WA (错误答案)。
- N^{\text{selected}} \geq 0
- 作业 ID 列表的长度必须为 N^{\text{selected}}.
- 指定的所有作业 ID 必须与存在的作业相对应。
- 指定的作业 ID 中没有重复项。
- 所有强制性工作(具有 f^\text{mandatory}=1) 必须包含在内。
- 对于所有选定的作业,如果它们依赖于 1 个或多个作业,则还必须选择这些作业。
输出示例
4 6 2 3 4
- 参赛者已接受
4工作。已接受作业的 ID 为6,2,3,4(N^{\text{selected}}=4,\text{id}_1=6,\text{id}_2=2,\text{id}_3=3,\text{id}_4=4).
输入 2(每个时间点)
如果输出 1 正确完成,则开始每个时间点的输入和输出。一切从时间开始 t=1,时间前进 1 此后每次该问题的进程都到达输入 2。
对于每个时间点,以下输入按如下所示的格式给出:
- 当前天气
- 已接受的作业数据
- 工人当前位置
- 天气预报(每个 T^\text{weather} 时间段)
w\\
N^\text{selected}\\
{\rm{id}}^{\rm{job}}_1\,\, n^{\rm{rest}}_1\\
\vdots\\
{\rm{id}}^{\rm{job}}_{N^\text{selected}}\,\, n^{\rm{rest}}_{N^\text{selected}}\\
{\rm{id}}^{\rm{worker}}_1\,\, u_1\,\, v_1\,\, d^{\rm{from\_u}}_1\\
\vdots\\
{\rm{id}}^{\rm{worker}}_{N_{\rm{worker}}}\,\, u_{N_{\rm{worker}}}\,\, v_{N_{\rm{worker}}}\,\, d^{\rm{from\_u}}_{N_{\rm{worker}}}
天气预报以以下格式在标准输入中给出, 对于每个 T^\text{weather} 时间段(换句话说,仅当时间 t 满足 (t-1) \mod T^\text{weather} = 0).
t_1\,\, p^1_1\,\, p^1_2\,\, \cdots \,\, p^1_{N^{\rm{weather}}}\\
t_2\,\, p^2_1\,\, p^2_2\,\, \cdots \,\, p^2_{N^{\rm{weather}}}\\
\vdots\\
t_{N'}\,\, p^{N'}_1\,\, p^{N'}_2\,\, \cdots \,\, p^{N'}_{N^{\rm{weather}}}
当前天气
- 输入
- 当前天气, w \in \{1,\cdots,N_\text{weather}\}在第一行给出。
输入示例
4
- 第 1 行:当时的天气状态 t is
4(w=4).
作业状态
给出了有关已接受作业的以下输入数据。
- 输入
- 接受的工作数量, N^\text{selected},在下一行给出。
- 每个作业的状态在下一个作业中给出 N^\text{selected} 行。这包括:
- 作业 ID:{\text{id}}^{\text{job}}_i
- 剩余任务数:n^{\text{rest}}_i
- 为 1 \leq i \leq N^\text{selected}.
输入示例
4 2 905 3 1052 4 653 6 737
- 第 1 行:参赛者接受的工作数量为
4(N^\text{selected}=4). - 第2行:参赛者接受了ID=的工作
2,其中有905剩余任务。 - 第3行:参赛者接受了ID=的工作
3,其中有1052剩余任务。 - 第4行:参赛者接受了ID=的工作
4,其中有653剩余任务。 - 第5行:参赛者接受了ID=的工作
6,其中有737剩余任务。
工人当前位置
- 输入
- 以下 N_\text{worker} 行提供工作人员数据:
- 工人 ID:\text{id}^\text{worker}
- 工作人员所在边两端的顶点索引: u,v
- 工人到顶点的距离 u: d^\text{from\_u}
- 以下 N_\text{worker} 行提供工作人员数据:
请注意,当工作人员不在边上而是在顶点上时,假设顶点是 w,那么 u=v=w 和 d^\text{from\_u}=0 将会得到满足。
输入示例
1 6 6 0 2 13 4 1 3 10 4 1 4 9 9 0 5 9 9 0
- 第 1 行:ID= 的工人
1位于顶点6(\text{id}^\text{worker}_1=1,u_1=6,v_1=6,d_1=0). - 第 2 行:ID= 的工人
2位于连接顶点的边上13和4,并且是1距顶点的单位距离13(\text{id}^\text{worker}_2=2,u_2=13,v_2=4,d_2=1) - 第3行:ID=的工人
3位于连接顶点的边上10和4,并且是1距顶点的单位距离10(\text{id}^\text{worker}_3=3,u_3=10,v_3=4,d_3=1) - 第 4 行:ID= 的工人
4位于顶点9(\text{id}^\text{worker}_4=4,u_4=9,v_4=9,d_4=0). - 第5行:ID=的工人
5位于顶点9(\text{id}^\text{worker}_5=5,u_5=9,v_5=9,d_5=0).
天气预报
仅当时间 t 满足 (t-1) \mod T^\text{weather} = 0,天气预报数据提供于 T^\text{weather} 间隔直至工作时间范围结束。
- 输入
- 让整数 N' 是当前时间之后的预测数 t。下一个 N' 行给出的数据如下:
- 时间 t_i 以及每种天气状态的概率 p^i_1\,\, p^i_2\,\, \cdots \,\, p^i_{N^{\text{weather}}} 时间 t_i ,截至当前时间(1\leq i \leq N').
- 让整数 N' 是当前时间之后的预测数 t。下一个 N' 行给出的数据如下:
请注意 t_i=t+(i-1)\times T^{\text{weather}},N'= (T_{\text{max}}-(t-1))/T^{\text{weather}}.
输入示例
以下是天气预报数据的示例 T_\text{max}=300,T^{\text{weather}}=10,N^{\text{weather}}=7,当时 231.
231 0 0 0 1 0 0 0 241 0.14018451203740215 0.1989275695057979 0.11416680823055275 0.47491922909498718 0.055436150269510279 0.013776723318683931 0.0025890075430656636 251 0.09280720088264463 0.12786225388899222 0.075541159856700776 0.2940084286639329 0.3187308679757298 0.073782875285869701 0.017267213446130077 261 0.13618507866780669 0.1738477285644548 0.085600288742176719 0.30613029252196533 0.23136324103370096 0.054225695397813925 0.012647675072081671 271 0.22147567372764859 0.26151152419242735 0.10180524115884333 0.30797314144503296 0.084544670039893785 0.018734568743877168 0.0039551806922769701 281 0.21773018584216544 0.25781470723187322 0.10129611879665416 0.30911960619088807 0.089756375035668315 0.020014729744938529 0.0042682771578124723 291 0.21391908801649892 0.25399316678508993 0.10069857638866596 0.30980462878477455 0.095541376935105796 0.021428548707005373 0.0046146143828596133
- 第 1 行:时间
231,天气状态为的概率 1 is0,对于 2 这是0,对于 3 这是0,对于 4 这是1,对于 5 这是0,对于 6 这是0,并且对于 7 这是0. - 第 2 行:在时间
241,天气状态为的概率 1 is0.14018451203740215,对于 2 这是0.1989275695057979,对于 3 这是0.11416680823055275,对于 4 这是0.47491922909498718,对于 5 这是0.055436150269510279,对于 6 这是0.013776723318683931,并且对于 7 这是0.0025890075430656636. - 第 3 行:在时间
251,天气状态为的概率 1 is0.09280720088264463,对于 2 这是0.12786225388899222,对于 3 这是0.075541159856700776,对于 4 这是0.2940084286639329,对于 5 这是0.3187308679757298,对于 6 这是0.073782875285869701,并且对于 7 这是0.017267213446130077. - 第 4 行:在时间
261,天气状态为的概率 1 is0.13618507866780669,对于 2 这是0.1738477285644548,对于 3 这是0.085600288742176719,对于 4 这是0.30613029252196533,对于 5 这是0.23136324103370096,对于 6 这是0.054225695397813925,并且对于 7 这是0.012647675072081671. - 第 5 行:在时间
271,天气状态为的概率 1 is0.22147567372764859,对于 2 这是0.26151152419242735,对于 3 这是0.10180524115884333,对于 4 这是0.30797314144503296,对于 5 这是0.084544670039893785,对于 6 这是0.018734568743877168,并且对于 7 这是0.0039551806922769701. - 第 6 行:在时间
281,天气状态为的概率 1 is0.21773018584216544,对于 2 这是0.25781470723187322,对于 3 这是0.10129611879665416,对于 4 这是0.30911960619088807,对于 5 这是0.089756375035668315,对于 6 这是0.020014729744938529,并且对于 7 这是0.0042682771578124723. - 第 7 行:在时间
291,天气状态为的概率 1 is0.21391908801649892,对于 2 这是0.25399316678508993,对于 3 这是0.10069857638866596,对于 4 这是0.30980462878477455,对于 5 这是0.095541376935105796,对于 6 这是0.021428548707005373,并且对于 7 这是0.0046146143828596133.
输出 2(每个时间点)
对于上述内容,参赛者必须在标准输出上输出以下内容:
- 每个工人的时间表
- 每个工人的一个操作
数据必须按以下格式输出。
N_\text{schedule}\\
\text{id}_1\,\,\text{id}_2\,\,\cdots\,\,\text{id}_{N_\text{schedule}}\\
\text{job}^{\text{id}_1}_t\,\,\text{job}^{\text{id}_1}_{t+1}\,\,\cdots\,\,\text{job}^{\text{id}_1}_{T_\text{max}}\\
\vdots\\
\text{job}^{\text{id}_{N_\text{schedule}}}_t\,\,\text{job}^{\text{id}_{N_\text{schedule}}}_{t+1}\,\,\cdots\,\,\text{job}^{\text{id}_{N_\text{schedule}}}_{T_\text{max}}\\
{\rm{action}}_1\\
{\rm{action}}_2\\
\vdots\\
{\rm{action}}_{N_{\rm{worker}}}
(在最后一行后插入换行符)
提交时间表
每个工人的作业执行计划以每个时间点的作业 ID 的形式维护。
参赛者必须同时提交所有工人的时间表 t=1。此后的任何时间,都可以重新提交仅需要更改的工作人员的计划。
-
输出
- 在第一行,输出需要更改计划的工人数量, N_\text{schedule}.
- 在下一行,输出工人的ID, \text{id}_1\,\,\text{id}_2\,\,\cdots\,\,\text{id}_{N_\text{schedule}}.
- 上下 N_\text{schedule} 行,输出ID=的worker的调度(每个时间点要执行的作业的ID)\text{id}_i,从当前时间开始 t 直到 T_\text{max}, \text{job}^{\text{id}_i}_t\,\,\text{job}^{\text{id}_i}_{t+1}\,\,\cdots\,\,\text{job}^{\text{id}_i}_{T_\text{max}}(1\leq i \leq N_\text{schedule}).
-
不满足以下条件将导致
WA(错误答案)。- N_\text{schedule} \geq 0
- 工作人员 ID 列表的长度必须为 N_\text{schedule}
- 指定的每个工作人员 ID 都必须有一个对应的工作人员。
- 工作人员 ID 不得重复。
- 假设提交时间为 t,计划中指定的作业 ID 数量必须为 T_\text{max}-t+1.
- 仅当时间 t=1: N_\text{schedule} = N_\text{worker}
重新提交日程时,日程附加积分的数量将根据变化程度减少一定数量(参见 时间表已加点).
工人行动
参赛者必须指定 \text{action}代表每个时间点的所有工人。 \text{action}以文本字符串的形式表示,共有三种类型。
stay:既不移动也不执行工作,留在当前位置。move w:移动距离 1 沿着从当前位置到顶点索引对应的顶点的最短路径w。如果不满足以下约束,将会导致WA(错误答案)。- 顶点索引对应的顶点
w必须存在。 - 当前位置不能是顶点
w.
- 顶点索引对应的顶点
execute i a:执行 ID= 的作业的任务i,a次。如果不满足以下约束,将会导致WA(错误答案)。- ID= 的作业
i必须包含在已接受的工作中。 - 工人当前位置必须与 ID= 的作业位置相同
i. - ID= 的作业类型
i必须包含在工作人员可以执行的工作类型中。 a必须是大于或等于 1 的整数。a不得超过 ID= 的作业的剩余任务量i.a不得超过执行任务数量的限制(请参阅 执行任务的限制 了解详细信息)。- ID= 的作业所在的作业
i取决于必须已完成。 - 奖励值必须为正数。
- ID= 的作业
对于 move w,如果当前位置和顶点之间有 2 个或更多不同的最短路径 w,没有指定如何选择。在这种情况下,参赛者可以通过重复选择并移动到路径上的点来选择所需的路径。
指定 \text{action} 与上述任何模式都不匹配的字符串将导致 WA(错误答案)。
另外,如果存在一些作业,其处理的总任务量超过其要完成的任务数 N^{\text{task}}_i,这将导致 WA or RE.
- 输出
- 对于以下内容 N_\text{worker} 行,输出动作, \text{action}_i,对于每个工人,其中 1 \leq i \leq N_\text{worker}.
输出示例
以下是一个示例 N_\text{worker}=3,T_\text{max}=10
示例 1:操作 + 初始计划提交 (t=1)
3 1 2 3 85 85 85 85 431 431 431 431 431 431 65 65 65 65 65 65 65 65 65 65 730 730 639 639 639 639 4 4 4 4 execute 85 135 move 12 move 98
- 第 1 行:参赛者正在提交赛程表
3工人。 - 第 2 行:适用的工人 ID=
1,2,3. - 第 3 行:这是第 2 行指定的第一个工作人员的时间表(ID=
1),如下:- 时间 1 执行 ID= 的作业
85。同样的时候 2 ID=85,当时 3 ID=85,当时 4 ID=85,当时 5 ID=431,当时 6 ID=431,当时 7 ID=431,当时 8 ID=431,当时 9 ID=431,并且在时间 10 ID=431.
- 时间 1 执行 ID= 的作业
- 第 4 行:这是第 2 行指定的第一个工作人员的时间表(ID=
2),如下:- 时间 1 执行 ID= 的作业
65。同样的时候 2 ID=65,当时 3 ID=65,当时 4 ID=65,当时 5 ID=65,当时 6 ID=65,当时 7 ID=65,当时 8 ID=65,当时 9 ID=65,并且在时间 10 ID=65.
- 时间 1 执行 ID= 的作业
- 第 5 行:这是第 2 行指定的第一个工作人员的时间表(ID=
3),如下:- 时间 1 执行 ID= 的作业
730。同样的时候 2 ID=730,当时 3 ID=639,当时 4 ID=639,当时 5 ID=639,当时 6 ID=639,当时 7 ID=4,当时 8 ID=4,当时 9 ID=4,并且在时间 10 ID=4.
- 时间 1 执行 ID= 的作业
- 第 6 行:指定当前时间 ID=1 的工作人员的操作:执行
135ID= 的作业的任务85. - 第7行:指定ID=2的worker当前的动作:向顶点移动
12. - 第8行:指定ID=3的worker当前的动作:向顶点移动
98.
示例 2:操作 + 无计划更改
0 stay move 87 execute 670 40
- 第 1 行:参赛者正在提交 0 个工人的时间表(即没有时间表更改)。
- 第2行:没有适用的工人,因此该行有0个工人ID(这是一个空行)。
- (缺少行:没有输出工作人员计划,因此没有输出行。)
- 第 3 行:指定当前时间 ID=1 的工作人员的操作:不执行任何操作。
- 第4行:指定ID=2的worker当前的动作:向顶点移动
87. - 第 5 行:指定当前时间 ID=3 的工作人员的操作:执行
40ID= 的作业的任务670.
示例 3:操作 + 时间表更改 (t=6)
2 2 3 65 65 65 65 223 639 4 4 91 91 execute 431 80 execute 65 40 move 9
- 第 1 行:参赛者正在提交日程更改
2工人。 - 第 2 行:适用的工人 ID=
2,3. - 第 3 行:这是第 2 行指定的第一个工作人员的时间表(ID=
2),如下:- 时间 6 执行 ID= 的作业
65。同样的时候 7 ID=65,当时 8 ID=65,当时 9 ID=65,并且在时间 10 ID=431.
- 时间 6 执行 ID= 的作业
- 第 4 行:这是第 2 行指定的第二个工作人员的时间表(ID=
3),如下:- 时间 6 执行 ID= 的作业
639。同样的时候 7 ID=4,当时 8 ID=4,当时 9 ID=91,并且在时间 10 ID=91.
- 时间 6 执行 ID= 的作业
- 第 5 行:指定当前时间 ID=1 的工作人员的操作。执行
80ID= 的作业的任务431. - 第 6 行:指定当前时间 ID=2 的工作人员的操作。执行
40ID= 的作业的任务65. - 第 7 行:指定当前时间 ID=3 的工作人员的操作。向顶点移动
9.
输入 3(评分)
完成后 输出 2 时间 t=T_\text{max},如果输出有效,则得分 S 在标准输入上按以下格式给出。
S
如果参赛者没有从标准输入读取该值,可能会导致 TLE.
排名方法详情请参见 排名方法
评分方法
分数 S 源自总奖励 R,未完成的惩罚 U,以及调度加点 A 根据以下公式。
S=\left\lfloor R \times U \times (1+\alpha A) \right\rfloor
请注意 \left\lfloor x \right\rfloor 表示floor函数,返回小于等于的最大整数 x.
~
的定义 R, U 和 A 如下。
奖励总额:
\begin{aligned} R=\sum_{j\in J_\text{finished}}\sum_{w \in W}\sum_{t=1}^{T_\text{max}}a^w_j(t)r_j(t) \end{aligned}
- 已完成作业集:J_\text{finished}
- 所有工人集:W
- 作业数量 j 工作人员执行的任务 w 时间 t:a^w_j(t)
- 工作的每项任务奖励 j 时间 t:r_j(t)
未完成作业的处罚:
\begin{aligned} U=\prod_{j \in J_{\text{unfinished}}} P^{\text{job}}_j \end{aligned}
- 已接受但未完成的作业集:J_\text{unfinished}
- 作业未完成惩罚因子 j:P_j^\text{job}
时间表已加点:
的初始值 A is 1.0 并根据以下规则在每个时间间隔更新:
-
对于每个工人:
- 如果工人执行的工作与计划不同:
\begin{aligned}A\leftarrow 0\end{aligned}
- 如果工作人员按计划执行相同的作业:
\begin{aligned}A\leftarrow A\end{aligned}
- 如果工人不执行工作:
\begin{aligned}A\leftarrow A\end{aligned}
- 如果工人执行的工作与计划不同:
-
如果工人的日程安排在某个时间重新提交 t:
- 获取当时的作业 ID s(\geq t):
- 如果更改,
\begin{aligned}A\leftarrow A\times \left(1.0-P_m \times (R_m)^{s-t}\right)\end{aligned}
- 如果不改变,
提交初始计划时,
\begin{aligned}A\leftarrow A\end{aligned}
- 如果更改,
- 获取当时的作业 ID s(\geq t):
请注意 A 不会更新。
对于空集,总和 \sum is 0,以及总产品 \prod is 1.
执行任务的限制
工作人员在一个时间点可以执行的任务数量由以下因素确定,具体取决于 工作人员可执行的最大任务数 L^\text{max}, 工作对天气的依赖性 d^\text{weather},和 天气状态 w \in \{1,\cdots,N_\text{weather}\}.:
\begin{aligned} L^\text{max}\times (1-d^\text{weather})^{c_w}\end{aligned}
在这里, c_w 是给出的限制因素 输入 1。请注意 0^0=1.测试用例生成规则
地理数据(图表)
-
术语
- 在这里,我们使用术语 分区 用于划分矩形区域的操作, [x_0,x_1]\times[y_0,y_1]\,\,(x_0<x_1,y_0<y_1),垂直和水平各半,分成四个较小的矩形。
- 具体来说,操作划分区域 [x_0,x_1]\times[y_0,y_1] 分为以下四块。
- [x_0,(x_1+x_0)/2]\times[y_0,(y_0+y_1)/2]
- [x_0,(x_1+x_0)/2]\times[(y_0+y_1)/2,y_1]
- [(x_1+x_0)/2,x_1]\times[y_0,(y_0+y_1)/2]
- [(x_1+x_0)/2,x_1]\times[(y_0+y_1)/2,y_1]
- 我们还定义了一个函数, \text{Split}(R),它执行此操作(从接收到的矩形区域给出上述区域集)。
-
参数
- 矩形区域大小:L>0
- 最大分区深度:d_\text{max} \in \mathbb{Z}_{\geq 0}
- (最大)矩形数量:M(整数 0 或更大, (4^{d_\text{max}+1}-1)/3 或更少)
- 距离最小刻度:s>0
- 切割面积比例:C\in (0,1]
-
生成程序1 (生成图表)
- 准备一组矩形区域, U=\{\}.
- 添加矩形区域 R=[0,L]\times[0,L] to U.
- If d_\text{max}=0,继续
8. - 从中选择一个矩形 U 随机并调用该矩形 r.
- 如果面积 r is L^2/4^{d_\text{max}},返回
4. - 添加所有元素 \text{Split}(R) to U.
- 如果这些元素已经在 即使添加 U, U 也不会改变。
- If |U| > M满意,继续
8.如果没有,返回4. - 创建一个加权、无向图, G=(V,E),W:E\rightarrow \mathbb{R}_{> 0},来自集合 A,中所有矩形的边的并集 U.
- 套装 图中顶点的 V 由集合中线段相交的所有点组成 A,所有边的并集。
- 边集 图中的 E 由所有顶点对组成 \{a,b\},其中 a\neq b 并且可以达到 b 来自 a 现场 A,所有边的并集,不经过任何其他顶点。
- 重量 W 是从点之间的欧几里得距离导出的。
- 这张图, G=(V,E) (带重量 W),用于生成地理数据。
(参考:Eisenstat, D.,随机道路网络:四叉树模型,第八届分析算法和组合学研讨会论文集 (ANALCO),第 76-84 页,2011 年(DOI:https://doi.org/10.1137/1.9781611973013.9))
- 生成程序2 (生成高程)
- 准备一个正方形区域, R=[0,1024]\times[0,1024].
- 除法 R by 128 在两者中 x 和 y 方向(创建 128\times128 方形区域大小 8\times8).
- 随机选择 20 这些方形区域来自 R 并调用它们的并集 A.
- 再次随机选择 20 这些方形区域来自 R 并调用它们的并集 B.
- 求解通过上述除法运算离散化的以下偏微分方程
2到时间 t=100000 (换句话说,计算 u(100000,x,y)):\displaystyle \frac{\partial u}{\partial t}=\Delta u-b(x,y)u+a(x,y)
时刻的初始值 t=0 is u(0,x,y)=u_0(x,y)\equiv 0,我们使用诺依曼边界条件。 a(x,y) 和 b(x,y) 定义如下:
a(x,y)=\begin{cases} 1/8^2, & \text{if}\ (x,y) \in A, \\ 0, & \text{otherwise}, \end{cases}
b(x,y)=\begin{cases} 1/8^2, & \text{if}\ (x,y) \in B, \\ 0, & \text{otherwise}. \end{cases} - 标准化 u(100000,x,y) 范围 [0,1], and use it as the elevation, e(x,y).
-
Generation procedure 3(cut the graph, distance scaling)
-
Match the elevation data 在程序2中生成的 e(x,y) 为图空间的大小, [0,L]\times[0,L]。 换句话说,定义空间尺度的高程 \tilde e(x,y),如 \tilde e(x,y)= e(L\times x/1024,L\times y/1024).
-
对于功能 H(z)=\{(x,y) \in [0,L]\times[0,L]|\tilde e(x,y)>z\}, which returns the parts where \tilde e(x,y) is larger than real value z, call the largest value of z for which the area of H(z) is C\times L^2 或更大, h.
- For the set of graph edges E 在生成过程1中生成,删除所有边 E 两端的两个顶点都在下面 h.
- Let the graph G'=(V',E') 是图的最大连通分量 G=(V,E).
- Define weight W':E' \rightarrow \mathbb{R}_{> 0}: 如下:W'(e)= s\times W(e)/\min_{e' \in E'}W(e')
- Use the graph G'=(V',E') (带重量 W') as the geographical data.
-
天气转变概率矩阵
这里我们描述生成转移概率矩阵的规则,其大小为 N^\text{weather}\times N^\text{weather} used for weather transitions.
- 参数
- 转移概率矩阵所需的平稳分布:\bm{s}^\text{sta}=(s^\text{sta}_1,s^\text{sta}_2,\cdots,s^\text{sta}_{N^\text{weather}})
- 矩阵的带宽(作为带状矩阵):d \geq 1
- Small value for convergence test:\epsilon > 0
- Maximum loop iterations:M\geq 1
- Intensity of diagonal component:q > 0
~
- 的 N^\text{weather}\times N^\text{weather} 矩阵 A is determined as follows:
Set the element a_{i,j} 在行 i 和专栏 j,至 a_{i,j}=\begin{cases} \exp(-q|i-j|^2), & \text{if}\ |i-j|\leq d,\\ 0, & \text{otherwise.} \end{cases}
- Normalize each row of A 因此总和是 1.
- Initialize the loop counter:l=0
- l\leftarrow l + 1
- If l>M,使用 A 作为转移概率矩阵并退出。
- Compute the stationary distribution \bm{s} of A.
- 设置矩阵 P 如下:
设置元素 p_{i,j} 在行 i 和专栏 j to p_{i,j}=\begin{cases} N^\text{weather}||\bm{s}^\text{sta}-\bm{s}||_\infty\max\{\epsilon,a_{i,j}\}\text{rand}(-1,1), & \text{if}\ |i-j|\leq d,\\ 0, & \text{otherwise.} \end{cases}
在这里, ||\cdot||_\infty 是最大范数,代表元素的最大绝对值。 \text{rand}(a,b) 表示来自均匀分布的随机数 [a,b]。计算每个元素时会生成随机数。 - Let the matrix A'=A+P
- 对所有行执行以下更新 A'。对于 i第行:
- 计算 m_i, the value of the smallest element.
- If m_i < 0,添加 -m_i 为列中所有元素的值 j which satisfy |i-j|\leq d.
- 规范化行,使总和等于 1.
- For each row in A',如果对角线分量不是唯一的最大分量,则返回
4. - 计算 \bm{s}',平稳分布 A'.
- If ||\bm{s}^\text{sta}-\bm{s}||_\infty > ||\bm{s}^\text{sta}-\bm{s'}||_\infty,更新 A by substituting A 与 A'.
- If the both conditions, "||\bm{s}^\text{sta}-\bm{s'}||_\infty < \epsilon N^\text{weather}”和“每个元素 a_{i,j} of A 在行 i 和专栏 j 满足 |i-j|\leq d, is positive.", are satisified, use A as the transition probability matrix and exit. If this is not the case, return to
4.
代表奖励的分段线性函数
For this problem, the function representing reward for each time (more accurately, the reward value per task) is expressed using linear interpolation between a finite number of points.我们将这些点称为控制点,生成有限数量的控制点的规则如下。
- 参数
- 正奖励部分的长度:L\geq 1
- Length for partitioning the interval:l\geq 1
- 奖励标准值:s > 0
- 生成控制点值时使用的标准偏差:\sigma' > 0
- 奖励上限:M > 0
- Reward lower limit:m > 0
~
- 设奖励开始时间为 b=\text{randint}(1,T_\text{max}-L),奖励结束时间为 e=b+L, and the number of segments be d=\text{round}(L/l)。在这里, \text{randint}(m,n) 是统一选择 m 到 n 之间的随机整数的函数,并且 \text{round}(x) 是一个返回值的函数 x rounded to the nearest integer.
- 生成 d+1 遵循对数正态分布的独立随机值 \mu=0 和 \sigma=\sigma',让他们成为 \{c_i\}_{i=1}^{d+1}.
- 定义 \{v_i\}_{i=1}^{d+1} by v_i=\prod_{j=1}^{i}c_j.
- 让 B=s\sqrt{(d+1)/\sum_{i=1}^{d+1}v_i^2},并定义 \{r_i\}_{i=1}^{d+1} by r_i=\text{round}(Bv_i).
- 如果存在 i 这样 r_i > M or r_i < m,返回
2. - 让 t_i=\text{round}(b+(i-1)L/d),并使用时间和奖励值对列表 ((b-1,0),(t_1,r_1),(t_2,r_2),\cdots,(t_{d+1},r_{d+1}),(e+1,0)) 作为控制点列表。
如果没有另外指定,则使用均匀随机分布。
排名方法
临时测试
对于临时测试, 50 test cases are randomly selected from the ones used for the system test and executed.然而,对于一种参数模式仅选择一种测试用例。
评估方法与系统测试相同。请参阅下面的系统测试部分。
系统测试
For the system test, some of the following characteristic parameters are given to satisfy the properties listed in the Remarks column:
| 因素 | 对应参数 | 类型数量 | 备注 |
|---|---|---|---|
| 工作时间长度 | T_\text{max} | 3 | 短(300),中(700), 长(1000) |
| 空间(地理数据)大小 测试用例生成规则中的 | d_\text{max} 在测试用例生成规则中 地理数据 | 3 | 小(5),中(6), 大(7) |
| 工人数量 | N_{\text{worker}} | 4 | 单(1), 几个(2),中等(5), 许多(10) |
| 所有作业数 | N_{\text{job}} | 3 | 几个(250 \leq N_{\text{job}} \leq 253 ),中等(500 \leq N_{\text{job}} \leq 503), 许多(1000 \leq N_{\text{job}} \leq 1003) |
| 未完成已接受工作的处罚 | P^{\text{job}}_i | 2 | 小([0.98,1.0)), 大([0.91,0.93)) |
| 天气波动 | q 在测试用例生成规则中 天气转移概率矩阵 | 3 | 少(2.0),适度(1.5),高度不稳定(1.0) |
| 总计:648 个图案 | 为每个模式生成 8 个测试用例 |
对于其中的每个模式, 8 生成具有不同种子值的测试用例,总共 3 \times 3 \times4\times 3 \times 2 \times 3 \times 8 = 5184 测试用例。
这只是上表中参数的模式生成。除了这个过程之外,还会为每个测试用例生成地理信息、工作等数据。
采用相对评价体系进行排名。对于每个测试用例,我们计算相对分数 \text{round}(10^{9} \times \frac{\text{YOUR\_SCORE}}{\text{MAX\_SCORE}}),其中 \text{YOUR\_SCORE} 是你的 分数 和 \text{MAX\_SCORE} 是该测试用例中所有参赛者获得的最高分。提交的分数是相对分数的总和。
如果您的提交产生无效输出或超出某些测试用例的时间限制,则只有这些测试用例的分数将为零。
系统测试将仅执行 上次提交收到的结果不是 CE。最后提交时请注意不要出错。
关于相关评价体系
在临时/系统测试中,将仅使用收到除以下结果之外的最后提交的结果来计算排名 CE 。在计算相对分数时,仅使用最后提交的内容来计算每个测试用例的所有参赛者中的最高分数。
排名中显示的分数是相对的,每当有新的提交到达时,所有相对分数都会重新计算。另一方面,提交页面上显示的每个提交的分数是通过将每个测试用例的分数相加而获得的绝对分数,并且不显示相对分数。为了了解当前排名中除最新提交之外的提交的相对分数,您需要重新提交。如果您提交的测试用例产生无效输出或超出时间限制,则提交页面中显示的绝对分数将变为 0,但排名显示正确回答的测试用例的相对分数总和。
约束
- 字符编码为 UTF-8(尽管仅使用 ASCII 字符)。
- 行尾代码是
LF(0x0A). - 分隔符是半角空格 (
0x20) - 允许使用尾随分隔符。
对于十进制值, [十进制] 附加 。
输入 1
- 300 \leq T_\text{max} \leq 1000 和 T_\text{max} 是的倍数 100
- 150\leq N_V\leq 2000
- 4N_V/3\leq N_E\leq 2 N_V
- 1\leq u_i,v_i\leq N_V, u_i \neq v_i (1 \leq i \leq N_E)
- 1\leq d_i \leq 128 (1 \leq i \leq N_E)
- 给出的图保证是连通的并且不包含自环或多边。
- 1 \leq N_\text{worker} \leq 10
- 1\leq v^\text{init}_i \leq N_V (1 \leq i \leq N_\text{worker})
- 30\leq L^\text{max}_i\leq 100 (1 \leq i \leq N_\text{worker})
- 1 \leq N^\text{JobType}_i \leq 3 (1 \leq i \leq N_\text{worker})
- 1\leq \text{Type}^i_j\leq 3 (1 \leq i \leq N_\text{worker},1 \leq j \leq N^\text{JobType}_i)
- 250 \leq N_\text{job} \leq 1003
- \text{ID}^\text{job}_i=i (1 \leq i \leq N_\text{job})
- 1\leq \text{Type}_i\leq 3 和 \text{Type}_i 包含在可处理的作业类型中 1 或更多工人。 (1 \leq i \leq N_\text{job})
- 500 \leq N^\text{task}_i \leq 1500(1 \leq i \leq N_\text{job})
- 1 \leq v^\text{job}_i \leq N_V (1 \leq i \leq N_\text{job})
- 0.91\leq P^\text{job}_i<1.0 (1 \leq i \leq N_\text{job}) [十进制] 附加
- f^\text{mandatory}_i\in\{0,1\}(1 \leq i \leq N_\text{job})
- 1 \leq N^\text{reward}_i \leq 43 (1 \leq i \leq N_\text{job})
- 0\leq t^\text{reward}_{i,1}<t^\text{reward}_{i,2}<\cdots<t^\text{reward}_{i,N^\text{reward}_i}\leq T_\text{max}+1(1 \leq i \leq N_\text{job})
- y^\text{reward}_{i,1}=y^\text{reward}_{i,N^\text{reward}_i}=0,1 \leq y^\text{reward}_{i,j} \leq 10^7 (1 \leq i \leq N_\text{job},2 \leq j \leq N^\text{reward}_i-1)
- 0\leq N^\text{depend}_i\leq 3(1 \leq i \leq N_\text{job})
- 1 \leq \text{id}^\text{depend}_{i,j} \leq N_\text{job},\text{id}^\text{depend}_{i,j} \neq \text{id}^\text{depend}_{i,k},\text{id}^\text{depend}_{i,j}\neq i (1 \leq i \leq N_\text{job},1\leq j \leq N^\text{depend}_i,1\leq k\leq N^\text{depend}_i,j\neq k)
- 作业依赖关系可以看作是一个有向无环图(不一定是连通的),每个作业作为顶点,作业之间的依赖关系作为有向边,每个连通分量的大小为 4 或更少。
- 5 \leq T^\text{weather} \leq 20 和 T^\text{weather} 划分 T_\text{max}.
- N^\text{weather}=7
- 0.0 \leq p^\text{weather}_{i,j} \leq 1.0,\displaystyle\sum_{k=1}^{N^\text{weather}}p^\text{weather}_{i,k}=1.0(1\leq i \leq N^\text{weather},1 \leq j \leq N^\text{weather}) [十进制] 附加
- (c_1,c_2,c_3,c_4,c_5,c_6,c_7) = (0,1,2,3,10,14,20)
- 0.005 \leq P_m< 0.025 [十进制] 附加
- 0.97< R_m \leq 0.999 [十进制] 附加 (注意分布 R_m 通过申请获得 f(x)=1.0-0.001 \cdot 30^x 到随机变量 X 遵循均匀分布 [0,1).)
- 0.2 \leq \alpha < 5 [十进制] 附加 (注意分布 \alpha 通过申请获得 f(x)=5^{-1+2x} 到随机变量 X 遵循均匀分布 [0,1).)
- 0.0 \leq d^\text{weather}_i < 0.15 (1 \leq i \leq N_\text{job}) [十进制] 附加
输入 2
- 1 \leq \text{id}_i^\text{job} \leq N_\text{job} (1\leq i\leq N^\text{selected})
- 0 \leq n^\text{rest}_i \leq N^\text{task}_i (1\leq i\leq N^\text{selected})
- 0.0 \leq L^\text{weather}_i \leq 1.0(1\leq i\leq N^\text{selected}) [十进制] 附加
- \text{id}^\text{worker}_i=i (1\leq i\leq N_\text{worker})
- 1\leq u_i,v_i\leq N_V (1\leq i\leq N_\text{worker})
- 0\leq d^\text{from\_u}_i \leq \text{Length of the corresponding edge} (1\leq i\leq N_\text{worker})
- u_i=v_i 当且仅当 d^\text{from\_u}_i=0. (1\leq i\leq N_\text{worker})
- 假设时间 输入 2 给出的是 t:
- N'= (T_{\text{max}}-(t-1))/T^{\text{weather}}
- t_i=t+(i-1)\times T^{\text{weather}} (1\leq i \leq N')
- 0.0 \leq p^i_j \leq 1.0,\displaystyle\sum_{k=1}^{N^\text{weather}}p^i_k = 1.0 (1\leq i \leq N') [十进制] 附加
输入 3(评分)
- 0 \leq S \leq 2^{63}-1
地理数据
- L=2048
- d_\text{max}\in\{5,6,7\}
- s=1
- 0.3 \leq C < 0.4 [十进制] 附加
- M=\text{round}(0.45(4^{d_\text{max}+1}-1)/(3\times 2^{d_\text{max}-5}))
转移概率矩阵
- \bm{s}^\text{sta}=(0.21,0.25,0.10,0.31,0.102,0.023,0.005) [十进制] 附加
- d=2
- \epsilon = 1.0 \times 10^{-8} [十进制] 附加
- M=10^6
- 1 \leq q \leq 2 [十进制] 附加
分段线性奖励函数
- 100 \leq L \leq T_\text{max}
- l = 25
- 10^6 \leq s \leq 2\times 10^6
- 0.3 \leq \sigma' < 0.38 [十进制] 附加
- M = 10^7
- m = 1
其他
- 天气的种子价值 \in \{0,1,\cdots,2^{64}-1\}
工具包
可以从以下位置下载解决此问题的工具包 这里。它包括以下内容:
- 判断程序(A、B均适用)
- 测试用例生成器(A 和 B)
- 示例代码(在 C++ 中,问题 A 和 B 各一个)
- 展示台
展示台
工具包中的判断程序生成的日志文件(JSON 格式)可用于可视化结果。
可视化工具包含在工具包中,但也可用 服务器上的 这里 。
有关详细信息,请阅读工具包中的 README 以及可视化工具页面底部的说明。