问题设置
概述
- 概念: 在本次编程竞赛中,您将运行送货服务。客户将向您的商店下订单。每个订单都有一个独特的 \text{ID} 并应交付给相应的客户。您的送货服务拥有一辆车。汽车将从商店取出订购的商品并将其交付给顾客。
- 分数: 您的目标是在给定的时间内尽快交付尽可能多的物品 T_{\text{max}}。 (订单预计截止到 0.95 \times T_{\text{max}}).
- 约束: 在本次比赛中,您可以放入车内的物品数量没有限制。然而,物品只能在下订单后从商店取货才能装载到车上。
- 问题 A/B: 在问题 A 中,所有订单位置和时间都提前提供给参赛者,参赛者算法应优化汽车的动作,以尽可能快地完成尽可能多的交付。另一方面,在问题B中,订单出现在网上,即出现新订单,同时您移动汽车以尽可能快地交付尽可能多的货物。
时间和空间规范:
- 时间: 在本次比赛中,我们通过整数值对时间进度进行建模 0 \le t < T_{\text{max}}.
- 地图: 在本次比赛中,我们通过简单、无向且连通的图对地图进行建模 G=(V, E),由一组顶点组成 V 和一组边 E
- 商店和顾客地点: 顶点 u \in V 标记为 1 to |V| 和顶点 u=1 表示您的商店的位置,而顶点 u = 2,...,|V| 表示潜在客户的位置。在这里, |V| 表示集合的元素数量 V.
- 街道: 每条边 \left\{ u, v \right\} \in E 表示连接顶点的街道 u, v \in V。相应的长度由整数边权重给出 d_{u, v} \ge 1.
- 图表创建: 基于随机种子生成地图的算法在以下伪代码中指定。有关更多详细信息,请参阅下面的示例代码。
伪代码: 地图图形生成器
- 输入:|V|, |E|, \mathrm{MaxDegree}=5
- 2d 顶点网格:
- 首先求最大整数 R>0 这样 |V| = R^{2} + r,与 r 是可能的最小非负整数。
- 然后我们绘制点 (x, y) 在 2d 顶点网格上 (0 \leq x, y \lt R).
- 对于每个点 (x, y) 添加统一随机偏移 dx, dy \in [0, 1] ,给出最终顶点位置 (x + dx, y + dy)\in [0,R] \times [0,R].
- 最后,添加剩余的 r 顶点位于均匀随机位置 (x, y) 与 0 \leq x, y \leq R.
- 顶点标签 u \in V 通过随机洗牌分配。店铺是顶点 u=1.
- 我们如何创建高速公路:
- 为了生成高速公路网络,我们创建一个完整的图 顶点集上的 G_{\text{comp}} 在顶点集上 u \in V,分配每个顶点对 u, v \in V \times V 欧几里德距离 W_{u, v} 作为边权重。
- 接下来,我们构造一个 最小跨度 树 G_{\text{comp}}。的 |V|-1 最小生成树的边是图的高速公路网络 G。我们分配每条边 \left\{ u, v \right\} 边权重 d_{u,v} \leftarrow \lceil 2 \times W_{u, v} \rceil .
- 我们如何添加支路:
- 为了创建支路网络,我们相继添加 |E|-(|V|-1) 图形的边 G 如下:
- 更新 \mathrm{cost}(u,v).
- 顶点对之间 \left( u, v \right) \in V\times V,尚未通过边连接,选择具有最小的一对 \mathrm{cost}(u,v).
- 分配边权重 d_{u,v} \leftarrow \lceil 4 \times W_{u, v} \rceil .
-
在这里, \mathrm{cost}(u,v) 本质上基于顶点的欧几里德距离,优先连接附近度数较低的顶点。此外,优先考虑沿矩形网格的支路,以避免过多的桥梁。详细定义如下:
- 定义 \mathrm{degree}(u),顶点的度数 u\in V 作为入射边的数量。
- 定义 \mathrm{color}(u) 对于每个顶点 u\in V 按照原来的位置 (x,y) 在顶点网格上为:
- If x+y 是偶数: \mathrm{color}(u) = 0
- If x+y 是奇数: \mathrm{color}(u) = 1
- 对于剩余的 r 顶点:分配颜色 \mathrm{color}(u) \in \left\{0,1\right\} 随机。
- 定义一个因素 f(u,v) 如下:
- If \mathrm{color}(u) 和 \mathrm{color}(v) 相同:设置 \mathrm{f}(u,v) = 5
- If \mathrm{color}(u) 和 \mathrm{color}(v) 不同:设置 \mathrm{f}(u,v) = 1
- 定义一个因素 g(u) 如下:
- If \mathrm{degree}(u) \lt \mathrm{MaxDegree} :设置 g(u)=1
- If \mathrm{degree}(u) \geq \mathrm{MaxDegree} :设置 g(u)=\infty
- 最后,成本定义如下:
- \mathrm{cost}(u,v) = W_{u,v}\times \mathrm{degree}(u) \times \mathrm{degree}(v) \times f(u,v) \times g(u) \times g(v).
- 为了创建支路网络,我们相继添加 |E|-(|V|-1) 图形的边 G 如下:
- 我们如何分配订单频率:
- 分配每个顶点 u \in V 订单频率 f_u \in \left\{0,1,2\right\}.
- 初始化商店顶点的订单频率: f_1 \leftarrow 0.
- 初始化其他顶点的顺序频率: f_u \leftarrow 1
- 现在确定阶次频率为 2 的顶点。为此绘制一个均匀的随机中心点 c=(c_x,c_y)\in [R/4,3R/4]\times[R/4,3R/4] 然后对于所有顶点 u=2,...,|V| 做:
- If \mathrm{EuclideanDistance}(c,u)\le R/8 + \mathrm{uniformRandom}[0,R/8]: f_{u} \leftarrow 2
汽车位置和移动规范:
为了进行送货,您将操作一辆送货车,它可以按照以下指定的方式占据位置并进行移动。
-
Car position: 汽车通常可以采取两种类型的位置:
- 在顶点上 u \in V.
- 在边缘 \left\{ u, v \right\} \in E。更具体地说,它位于一个距离 x (0 \lt x \lt d_{u, v}) 来自 u to v .
-
汽车移动: 每一步 0 \le t < T_{\text{max}} 您必须选择以下操作之一才能控制您的送货车。
stay:停留在当前位置。move w:向顶点迈出一步 w \in V.
如果选择
move w, w 必须遵守以下约束。不遵守这些限制会导致错误的答案WA.- w 必须是一个顶点,即 w \in V.
- 如果汽车位于顶点 u \in V,必须有一条边连接 u 和 v,即 \left\{ u, w \right\} \in E.
- 如果汽车在边缘 \left\{ u, v \right\} \in E, w must either be w = u or w = v.
订单、交货和限制:
- 订单: 在整个比赛中,每个订单都具有三个数量的特征:唯一的订单 ID、顶点 v \in V 表示订单目的地和订单时间 t 订单出现的位置。详细格式见下文。
- 订单生成: 每次 0 \le t \le T_{\text{last}} = 0.95 \times T_{\text{max}} 最多可出现 1 个新订单 p_{\text{order}}(t)。如果有订单,则订单目的地 i 从顶点集中选择 V 概率与订单频率成正比 f_i。有关详细信息,请参阅下面的伪代码或下面的示例代码。
伪代码: 订单生成
- 输入: 最后下单时间 T_{\text{last}} 和平均订单概率 p_{\text{order}}(t).
- 初始化: \mathrm{ID} \leftarrow 0.
- 对于每个步骤 t = 0, ..., T_{\text{last}} 做:
- 生成统一随机数 r \in [0,1] .
- If r \le p_{\text{order}}(t) :
- 选择顶点位置 u \in V 随机,概率与订单频率成正比 顶点的 f_{u} 。
- \mathrm{ID} \leftarrow \mathrm{ID} + 1
- 下单(新订单ID、下单时间 t,顶点位置 u \in V )
- 其他: 未下订单
- 注意: 平均订单概率定义如下:
- p_{\text{order}}(t) = \begin{cases} t / T_{\text{peak}}, & \text{if } 0\le t \lt T_{\text{peak}}, \\ (T_{\text{last}} - t) / (T_{\text{last}}- T_{\text{peak}}), & \text{if } T_{\text{peak}} \le t \lt T_{\text{last}}, \\ 0, & \text{if } T_{\text{last}} \le t, \end{cases}
- 其中 T_{\text{last}}:=0.95 \times T_{\max} 和 T_{\text{peak}} 是从区间中随机均匀抽取的 [0, T_{\text{last}}].
- 注:值 T_{\text{peak}} 将不会作为输入给出。
- 交货: 要交付订单,参赛者必须在下订单后执行以下步骤:
- (1st) 将车移至商店: 注意:将汽车移入商店时,所有下单时间小于或等于当前时间的订单都会转移到汽车中。另一方面,尚未出现的订单则无法放入车内。
- (2) 将车移至客户位置: 要完成交付,请将汽车移动到客户位置的顶点。注意:尚未转移到车上的订单,即使您到达了顾客位置,也不会被交付。
- 限制: 在整个比赛中,我们假设每个订单都有一个唯一的 \text{ID} 并应交付给相应的客户。进一步假设车内可以下无限数量的订单。
评分
- 比赛期间,提交的总分是通过将 30 个输入案例的提交分数相加来确定的。
- 比赛结束后将进行系统测试。为此,参赛者 最后提交 将通过对 100 个以前未见过的输入案例提交的分数求和来进行评分。
- 对于每个输入案例,分数计算如下:
\text{Score} = \sum_{i \in D} {(T_{\text{max}})}^{2} - {(\mathrm{waitingTime}_i)}^{2},
这里我们使用以下定义:- D :交付的订单集直到 t=T_{\text{max}}
- 的等待时间 i第订单: \mathrm{waitingTime}_i = \mathrm{deliveredTime}_i - \mathrm{orderedTime}_i.
- 请注意,输入情况给出输出
WA将收到 0 点。
问题B的详情:
问题 B 是 互动 竞赛,参赛者代码连续接收来自主机代码的新生成和交付订单的更新,同时通过在每一步中将汽车移动到相邻位置来为客户提供服务 t=0,...,T_{\max}-1。详细描述了参赛者和主机代码交互的精确流程如下所示。
| 参赛者代码 | 主机代码 | |
|---|---|---|
| 生成并输出图表 G | ||
| + | 时间 t: 生成并输出新订单 | |
| + | 时间 t:如果在商店,输出装载到汽车中的订单 | |
| + | 时间 t: 确定并输出一步棋 | |
| + | 检查移动的可行性;如果移动不可行:输出 NG,如果可行:输出 OK |
|
| + | 时间 t+1:更新并输出已交付物品的信息(如果有) |
注意:主机代码仅输出图形一次。表左侧用“+”标记的过程对于整数迭代重复 t in t = 0,..., T_{\max} - 1.
标准 IO 的输入/输出格式
首先,主机代码会输出一个图表 G,阶次频率 f_{i} 对于每个顶点 i,与订单出现在顶点的概率成正比 i,以及总步数 T_{\max}.
|V| |E|
u_1 v_1 d_{u_1, v_1}
u_2 v_2 d_{u_2, v_2}
\vdots
u_{|E|} v_{|E|} d_{u_{|E|}, v_{|E|}}
f_1 f_2 \ldots f_{|V|}
T_{\max}
- 第一行: |V| 顶点数, |E| 边数
- 下一个 |E| 线:图形的边缘。特别是, i第行表示顶点 u_i 和 v_i 形成一条边,以及相应的边权重 d_{u_i, v_i}.
- 下一行:订单频率 f_i 确定顶点处订单的概率 i as p_{i}=\frac{f_{i}}{\sum_{i}f_{i}}.
- 最后一行:汽车更新总数 T_{\max}.
时间 t 我们首先通过标准输入获取以下信息。
N_{\text{new}}
\mathrm{new\_id}_1 \mathrm{dst}_1
\mathrm{new\_id}_2 \mathrm{dst}_2
\vdots
\mathrm{new\_id}_{N_{\text{new}}} \mathrm{dst}_{N_{\text{new}}}
N_{\text{put}}
\mathrm{put\_id}_1
\mathrm{put\_id}_2
\mathrm{put\_id}_{N_{\text{put}}}
- N_{\text{new}} 代表该时间出现的新订单数 t.
- 下一个 N_{\text{new}} 行给出了新生成的订单信息。的 i第订单信息表示订单ID 新订单的 \mathrm{new_{id}}_i ,同时 \mathrm{dst}_i 表示客户希望将订单交付到的顶点。
- N_{\text{put}} 代表当时转移到车上的物品数量 t.
- 如果汽车不在商店的顶点 N_{\text{put}} 将为零。
- 后续 N_{\text{put}} 行表示新加载项目的订单信息。特别是, i第行表示车上装载的产品对应的订单ID为 \mathrm{put_{id}}_i.
接下来,为了将送货车移动到相邻位置,参赛者代码每次都必须 t (0 \leq t \lt T_{\max})输出以下内容 \mathrm{command} 到标准输出。
\mathrm{command}
在这里, \mathrm{command} 必须采用以下形式
- 如果您想让汽车
stay在当前位置,发送-1到标准输出 - 如果你想让汽车向邻近的顶点移动一步
move w,发送w到标准输出
注意:如果您选择 move w, w 必须满足以下所有条件。如果违反以下任一条件,主机代码将输出 NG 并且参赛者应终止该计划,最终导致 WA (不正确)。
- w 是一个顶点索引 w \in \left\{1, ... , |V|\right\}
- 如果汽车位于顶点 u,边缘 \left\{ u, w \right\} \in E 必须存在
- 如果汽车处于边缘 \left\{ u, v \right\}, w must either be w = u or w = v
在您执行操作后的时间 t 发送到标准输出,主机代码将发送以下有关时间的信息 t + 1 到标准输入。
\mathrm{verdict}
N_{\text{achieve}}
\mathrm{achieve\_id}_1
\mathrm{achieve\_id}_2
\vdots
\mathrm{achieve\_id}_{N_{\text{achieve}}}
- \mathrm{verdict} 是一个字符串,指示您当时的操作是否 t 有效。它可以是以下两个选项之一。
OK:表明你的行动是可行的NG:表示您的操作不可行。如果您收到此输入, 您必须立即终止该程序。 如果立即终止,则保证为 WA(不正确)。如果不立即终止,则行为未定义。
- N_{\text{achieve}} 代表该时刻已发货的订单数量 t.
- 如果汽车不在交付顶点,则没有订单已交付并且 N_{\text{achieve}}=0.
- 后续 N_{\text{achieve}} 行表示已交付的订单。特别是, i第行表示订单ID \mathrm{achieve\_{id}}_i.
最后,在最后一步之后接收到主机代码的标准输入后 T_{\max} 您必须立即终止该程序。
约束
I/O 限制
- 通过标准输入给出的所有数字都是整数。
- 所有输出必须是整数
- T_{\text{max}} = 10000
- 200 \leq |V| \leq 400
- 1.5 |V| \leq |E| \leq 2|V|
- 1 \leq u_{i}, v_{i} \leq |V| (1 \leq i \leq |E|)
- 1 \leq d_{u_i, v_i} \leq \lceil 4\sqrt{2|V|} \rceil (1 \leq i \leq |E|)
- 给定的图没有自环,没有重边,并且保证是连通的。
- f_1 = 0
- f_i \in \left\{ 1, 2 \right\} (2 \leq i \leq |V|)
- \mathrm{verdict} \in \left\{ \text{"OK"}, \text{"NG"} \right\}
- 0 \leq N_{\text{new}} \leq 1
- 1 \leq \mathrm{new\_id}_{i} \leq T_{\text{last}}+1 (1 \leq i \leq N_{\text{new}})。注:如果所有订单均按上述订单生成规则生成,则订单总数最多为 T_{\text{last}}+1。因此,可能的范围为 \mathrm{new\_id}_{i} 应该来自 1 to T_{\text{last}}+1.
- 订单 ID \mathrm{new\_{id}}_i 是独一无二的。
- 2 \leq \mathrm{dst}_i \leq |V| (1 \leq i \leq N_{\text{new}})
- 参赛者在某个时刻输出到标准输出的整数 t must either be -1 or 1 \leq w \leq |V|
输入/输出示例
| 时间 | 参赛者 | 主机代码 | 说明 |
|---|---|---|---|
5 7 1 2 5 5 3 4 2 4 8 1 5 1 2 3 3 4 5 3 4 3 9 0 1 1 5 5 500 |
首先,主机代码通过标准输入提供图形数据。在这个例子中,图表有 |V| = 5 顶点和 | E | = 7 边缘。接下来,在一行中给出每个顶点的阶频率。最后, 给出了 T_{\max} 。 | ||
| 0 \rightarrow 1 |
1 1 5 1 1 |
时间 t=0 我们收到一份订单。该订单有ID= 1 并且应该传递到顶点 5。由于您的汽车当前位于顶点一,因此订单将自动转移到您的汽车中。这样,当您的汽车到达商店时,当前和之前下的所有订单都会自动加载到您的汽车中。 | |
2 |
你决定向顶点移动一步。 | ||
OK 0 |
第一行表明你的举动是可行的。第二行显示没有订单已交付。 | ||
| 1 \rightarrow 2 |
1 2 2 0 |
1 个新订单(ID =2,交付顶点 =2)已发生。你的车在顶点之间的边缘 1 和 2,因此零订单已转移到您的汽车上。 | |
-1 |
您决定将您的车保持在同一位置。 | ||
OK 0 |
你的举动是有效的。不会交付任何订单,因为您不在交付项目位置。 | ||
| 2 \rightarrow 3 |
1 3 4 0 |
一个新订单(ID =3,交付顶点 =4)已出现。 | |
1 |
你决定向顶点后退一步 1。这样您就可以掉头了。 | ||
OK 0 |
尚未交付任何订单。 | ||
| 3 \rightarrow 4 |
0 2 2 3 |
由于汽车已返回商店,因此订单 ID 2 和 3 对应的产品已装载到汽车上。 | |
5 |
参赛者决定向顶点 5 移动一步。 | ||
OK 1 1 |
自从您到达顶点 5 以来,带有 ID 的订单 1 已交付。 | ||
| 4 \rightarrow 5 |
0 0 |
没有新订单。 | |
5 |
参赛者决定向顶点移动一步 5. | ||
NG |
输入无效,您应该终止程序。 |
使用标准输出
将移动指令返回到标准输出时,请使用flush命令。作为示例,考虑您要输出的情况 -1。这是在一些主要编程语言中执行此操作的方法。
C++
std::cout << "-1" << std::endl;
Java
System.out.println("-1");
Python 3.4
print("-1", flush=True)