← 返回题目列表

AtCoder · hokudai_hitachi2019_2_a

A. 问题C

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

问题设置

概述

  • 概念: 与第一个类似 竞赛,参赛者将经营送货服务。顾客将向参赛者商店下订单。每个订单都有一个独特的 \text{ID} 并应交付给相应的客户。参赛者的送货服务拥有一辆车。汽车将从商店取出订购的商品并将其交付给顾客。
  • 分数: 目标是在给定的时间内尽可能快地交付尽可能多的物品 T_{\text{max}}。 (订单预计截止到 0.95 \times T_{\text{max}}).
  • 约束: 在本次比赛中,可以放入车内的物品数量没有限制。然而,物品只能在下订单后从商店取货才能装载到车上。
  • 问题C: 在这个问题中,订单出现在网上,即出现新订单,而参赛者则移动汽车以尽可能快的速度进行尽可能多的送货。此外,服务的规划算法必须掌握一些环境不确定性,这是与我们之前的比赛的主要区别。
  • 新: 环境不确定性:
    • 交通堵塞 可能会出现在高速公路沿线。
    • 汽车故障: 送货车可能会坏。
    • 订单取消: 客户可以在一定时间后取消订单。
    • 交通灯 可能会阻碍汽车进入和穿越高速公路。
overview

时间和空间规范:

  • 时间: 在本次比赛中,我们通过整数值对时间进度进行建模 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.
  • 新: 图表创建: 下面的伪代码指定了基于随机种子生成地图的算法。有关更多详细信息,请参阅下面的示例代码。注:图生成算法与之前的比赛不同。
额外信息和伪代码: 地图图形属性和地图图形生成器 本次比赛中使用的地图生成器生成具有以下属性的地图:
  • 该图具有明显的二维结构 25\times25 顶点。
  • 新: 每个图表都有两条高速公路路径,将北端之一连接到南端之一,以及将东端之一连接到西端之一。沿着高速公路行驶大约是 比在其他道路上行驶快 4 倍。
  • 新: 此外,从地图的北端到南端有一条新的瓶颈线。
  • 新: 高速公路和瓶颈线将图划分为 6 个稀疏连接的区域。
  • 典型顶点具有相对顺序频率 1,而某个集中区域的订单频率 2。订单既不会出现在高速公路上,也不会出现在商店顶点上。两者都有订单频率 0.
overview
早期施工阶段的典型地图(左)和最终形状的(右)。 (左):具有南北向和东西向高速公路(黑色点和线)的顶点网格(点)和一条(虚线)瓶颈线将其余顶点划分为 6 个不相交的顶点集(绿色阴影背景)。高速公路从交叉点起每 5 步与邻近区域相连。瓶颈线东西两侧的区域也从瓶颈线与东西高速公路交汇处每隔五步相连。 (右):最终地图,包含 2 条高速公路(粗灰线)和最终顶点位置。不在高速公路上的粉红色顶点具有相对顺序频率 1。中心区域的绿色顶点具有有序频率 2.

地图图形生成器的伪代码:
  • 输入:|V|, |E|, \mathrm{MaxDegree}=5
  • 2d 顶点网格:
    • 设置 R \leftarrow \lfloor \sqrt{|V|} \rfloor。 (下面我们假设这种情况 |V| = R \times R。对于潜在余项的处理,请查阅工具包中的代码。)
    • 情节要点 (x, y) 在 2d 顶点网格上 (0 \leq x, y \lt R) 如下。 \forall u\in{1,...,|V|}
      • x \leftarrow (u-1) \mod R
      • y \leftarrow \frac{u-1-x}{R}
    • 最后,我们随机打乱顶点标签 u。店铺是顶点 u=1.
  • 高速公路和瓶颈线
    • 分配了南北高速公路顶点路径。为此我们选择 一 x\in[R/2, 2R/3] 并将所有顶点分配给相应的 x 到路径。相邻高速公路顶点与 d_{u,v}\leftarrow 1。 (见图。)
    • 类似地,分配东西向高速公路顶点路径。为此我们选择一个 y\in[R/3, 2R/3] 并将所有顶点分配给相应的 y 到路径。相邻高速公路顶点与 d_{u,v}=1。 (见图。)
    • 四个高速公路方向分别指定为高速公路的北、南、东、西方向。
    • 最后,瓶颈线分配在 x=\xi+0.5,其中 \xi\in[R/6,R/3] (均匀随机)。 (见图。)
    • 高速公路和瓶颈线将顶点网格的剩余顶点分为 6 地区。 (见图。)
    • 与高速公路相邻的区域每五个高速公路顶点(从高速公路交叉口算起)与高速公路相连。
    • 类似地,瓶颈线以东和以西的区域每五个顶点对连接一次(从东西高速公路与瓶颈线的交点开始计算)。
  • 最终顶点位置:
    • 创建高速公路、高速公路入口和跨越瓶颈线的连接后,通过添加统一随机偏移将顶点移动到最终顶点位置 dx, dy \in [0, 1] ,给出最终顶点位置 (x + dx, y + dy)\in [0,R] \times [0,R].
  • 我们如何在区域内创建互联的道路网络 6 次区域:
    • 为了在六个分区内生成连接的道路网络,我们创建了一个完整的图 顶点集上的 G_{\text{comp}} 在顶点集上 u \in V,分配每个顶点对 u, v \in V \times V 边权重 W_{u, v} 如下:
      • W_{u, v}\leftarrow 1 用于高速公路边缘 所有顶点对的顶点位置的
      • W_{u, v}\leftarrow \mathrm{EuclideanDistance} 所有顶点对的顶点位置 u,v 两者 u 和 v 在同一区域内。
      • 先前指定的穿过瓶颈线并进入高速公路的边也被指定了相应顶点位置的欧几里得距离。
      • 最后, W_{u, v}\leftarrow \infty,对于顶点位于相互不同区域的所有剩余顶点对。
    • 接下来,我们构造一个 最小跨度 树 G_{\text{comp}},通过将先前已分配的边(高速公路、高速公路入口和跨瓶颈线的连接)扩展到完整的树。的 |V|-1 最小生成树的边给出一个连通图。边缘权重 d_{u,v} \leftarrow \lceil 4 \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
      • 定义一个因素 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).
  • 我们如何分配订单频率:
    • 分配每个顶点 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
    • 最后,对于所有顶点 u 沿高速公路,指令频率设置为: f_u \leftarrow 0.

汽车位置和移动规范:

为了进行送货,您将操作一辆送货车,它可以按照以下指定的方式占据位置并进行移动。

  • 车位: 汽车通常可以采取两种类型的位置:

    • 在顶点上 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 必须遵守以下约束。如果违反以下任一条件,主机代码将输出 NG 并且参赛者应终止该计划,最终导致 WA (错误答案)。

    • w 必须是一个顶点,即 w \in V.
    • 如果汽车位于顶点 u \in V,必须有一条边连接 u 和 v,即 \left\{ u, w \right\} \in E.
    • 如果汽车在边缘 \left\{ u, v \right\} \in E, w 必须是 w = u or w = v.

  • 新: 如果参赛者沿着因交通拥堵而阻塞的高速公路方向移动,则参赛者的移动可能会被拒绝。

  • 新: 进入高速公路后,参赛者可能需要在红绿灯处等待。
Car position and moves

订单、交货和限制:

  • 订单: 在整个比赛中,每个订单都具有三个数量的特征:唯一的订单 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) 将车移至客户位置: 要完成交付,请将汽车移动到客户位置的顶点。注意:尚未上车的订单或已取消的订单,即使您到达顾客位置,也不会发货。
constraint image
  • 限制: 在整个比赛中,我们假设每个订单都有一个唯一的 \text{ID} 并应交付给相应的客户。进一步假设车内可以下无限数量的订单。

  • 新: 不耐烦的客户可能会取消订单。详情请参阅下面的活动部分。

新: 环境的不确定性

交付计划必须掌握几个环境不确定因素

  • 交通堵塞 可能会出现在高速公路沿线。如果出现新的交通堵塞,它会完全阻塞四个可能的高速公路方向之一。需要注意的是,沿着高速公路方向行驶的汽车因交通堵塞而被阻挡,只能在 10\% 的案例。在 90\% 的情况下,它将被迫留在当前位置。具体请参见伪代码或分布式工具包中的代码。

    伪代码: 交通堵塞
    • 鉴于: p_{\text{duration}}(t) // 交通拥堵持续时间分布。
    • 鉴于: p_{\text{delay}}(t) // 延迟时间分布,描述高峰点之后交通拥堵爆发的延迟。
    • 输入: p_{\text{jam}}=0.25 // 单一交通拥堵爆发的概率。
    • 输入: p_{\text{move}}=0.1 // 接受汽车沿着高速公路拥堵方向移动的概率。

      // 初始化时处理交通拥堵
    • 对于四个高速公路方向中的每一个 d=1,2,3,4 我们采样四个时间点 t_{d,i} 与 i=1,2,3,4 来自均匀随机分布并及时排序。
      • t_{d,i} \sim \mathrm{uniformRandom}[0,T_{\max})
      • \forall d : t_{d,1} \le t_{d,2} \le t_{d,3} \le t_{d,4}
    • 每个 t_{d,i} 定义了一个时间点,在此时间点之后可能会出现交通堵塞 p_{\text{jam}}。如果发生交通拥堵,则会延迟一段时间,描述为 p_{\text{delay}}(t) 并具有由下式描述的持续时间 p_{\text{duration}}(t) 如下:
      • 对于所有对 (d,i) 与 d = 1,...,4 和所有 i = 1, ..., 4 做:
        • if \mathrm{uniformRandom}[0,1] \le p_{\text{jam}}: // 出现交通拥堵
          • 采样延迟: \delta_{d,i} \sim p_{\text{delay}}(t)
          • 沿途堵车 d 将从以下时间开始: t_{\text{start}, d, i} \leftarrow t_{d,i} + \delta_{d,i}
          • 采样持续时间: \Delta_{\text{jam}, d, i} \sim p_{\text{duration}}(t)
          • 沿线方向堵车 d 将结束于: t_{\text{end}, d, i} \leftarrow t_{\text{start}, d, i} + \Delta_{\text{jam}, d, i}
        • Else: // 没有出现交通拥堵

  • 对于每个方向的间隔 [t_{\text{start}, d, i}, t_{\text{end}, d, i}] 收集在列表中。注:重叠间隔统一。
  • 参赛者算法将获得全部 16 个 t_{d,i} 作为输入。另一方面,堵车间隔 初始化时不会提供 [t_{\text{start}, d, i}, t_{\text{end}, d, i}] 。

    // 线上配送阶段堵车的处理
  • 对于 t=0,..., T_{\max}-1 做:
      // 通知参赛者交通堵塞
    • 对于 d=1,2,3,4 做:
      • If t 处于交通拥堵区间之一 t\in [t_{\text{start}, d, i}, t_{\text{end}, d, i}]:
        • 发送 \mathrm{jam}_d=1 致参赛者
      • 其他:
        • 发送 \mathrm{jam}_d=0 致参赛者
      // 处理参赛者的动作
    • 照常检查移动的有效性。
    • 如果(无交通拥堵):按照指示移动汽车。
    • 否则如果(汽车在高速公路上)并且(朝方向移动) d)和(方向 d 堵车):
      • If \mathrm{randomUniform}[0,1] \le p_{\text{move}}:
        • 接受移动、更新位置和输出 OK 通知参赛者
      • 其他:
        • 拒绝移动,停留在当前位置,并输出 JAM 通知参赛者

  • 交通拥堵持续时间呈指数分布,平均值为 \mu=1000。有关更多详细信息,请参阅下面对发行版的评论或查看工具包。
  • 交通拥堵延误的分布是幂律分布,其特征为 \mathrm{median}=100 及其指数特征为 \epsilon=3。有关更多详细信息,请参阅下面对发行版的评论或查看工具包。
  • 汽车故障: 送货车可能发生故障。在汽车抛锚前几步,参赛者会收到 WARNING t 保证用户 t 返回商店修理汽车的步骤。如果参赛者未能在规定时间内返回商店,参赛者将收到 BROKEN 信号,小车在 300 步内无法移动。具体请参见伪代码或分布式工具包中的代码。

    伪代码: 汽车故障
    • 鉴于: 汽车正常时间分布 p_{\text{car ok}}(t).
    • 鉴于: 首次车辆故障报警返回时间 T_{\text{warning}}.
    • 初始化: t_{\text{car}} \sim p_{\text{car ok}}(t) 和 \mathrm{carStatus} = 0 // 车好
    • 对于 t=0,..., T_{\max}-1 做:
        // 小车状态切换
      • if \mathrm{carStatus} == 0 和 t_{\text{car}} == 0: // 进入警告状态
        • t_{\text{car}} \leftarrow T_{\text{warning}}
        • \mathrm{carStatus} \leftarrow 1 //警告状态
      • if \mathrm{carStatus} == 1 和 t_{\text{car}} == 0: // 进入车坏状态
        • t_{\text{car}} \leftarrow 300
        • \mathrm{carStatus} \leftarrow 2 //车坏了
      • 如果(\mathrm{carStatus} == 1 并且当前位置是商店顶点)或 (\mathrm{carStatus} == 2 和 t_{\text{car}} == 0:) // 修理汽车
        • t_{\text{car}} \leftarrow p_{\text{car ok}}(t)
        • \mathrm{carStatus} \leftarrow 0 //车没坏
      • // 发送信号状态
      • if \mathrm{carStatus} == 0:发送 NOT_BROKEN
      • if \mathrm{carStatus} == 1:发送 WARNING t // t = t_{\text{car}}
      • if \mathrm{carStatus} == 2:发送 BROKEN
      • // 接收参赛者的动作
      • \mathrm{move} \leftarrow 来自参赛者
      • // 处理参赛者的动作
      • if \mathrm{carStatus} \in \{0,1\} :标准程序
      • 如果(\mathrm{carStatus} == 2 和 \mathrm{move} 不是 -1:)
        • 发送: NG // 通知参赛者无效动作
      • //递减定时器
      • t_{\text{car}} \leftarrow t_{\text{car}} - 1
      注意:
    • p_{\text{car ok}}(t) 生成随机变量,其逆数是从幂律分布中采样的 \mathrm{median} = \frac{1}{T_{\max}} 和指数特征为 \epsilon = 2.5。有关更多详细信息,请参阅下面对发行版的评论或查看工具包。
    • If \mathrm{carStatus} == 0 然后 t_{\text{car}} 参赛者未知。
    • If \mathrm{carStatus} == 2,即车坏了,参赛者代码必须发送输入 -1 (stay),否则结果将是 WA (错误答案)。

  • 订单取消: 等待订单时间超过 T_{\text{wait}}=2000 步骤中,允许取消其订单。订单取消按概率进行处理,如以下伪代码所述。有关更多详细信息,请参阅分布式工具包。

    伪代码: 订单取消
    • 鉴于: T_{\text{wait}}=2000 以及额外等待时间的分配 p_{\text{extra}}(t).
    • 对于 t=0,..., T_{\max}-1 做:
        // 生成订单时 \text{ID}:
        • 示例: t_{\text{extra}} \sim p_{\text{extra}}(t)
        • t_{\text{cancel}}(\text{ID}) \leftarrow t + T_{\text{wait}} + t_{\text{extra}}
        // 更新订单时:
        • 对于每个未送达的订单 \text{ID} 做:
          • if t_{\text{cancel}}(\text{ID}) < t : 发送订单取消信号

    • 注1: 参赛者不知道 t_{\text{extra}} 和 t_{\text{cancel}}(\text{ID}) 。
    • 注2: p_{\text{extra}}(t) 生成随机变量,其逆数是从幂律分布中采样的 \mathrm{median} = \frac{1}{T_{\max}} 和指数特征为 \epsilon=0.5。有关更多详细信息,请参阅下面对发行版的评论或查看工具包。

  • 交通灯: 进入高速公路时,汽车可能必须在红绿灯处等待。特别是,根据时间,定期授予从高速公路外部的顶点到构成高速公路的顶点的访问权。 t。请注意,这也会影响仅穿过高速公路的汽车。具体可以参考下面的伪代码或者分布式工具包。

    伪代码: 交通灯
    • 输入: 信号周期 P_{\text{light}}
    • 对于 t=0,..., T_{\max}-1 做:
      • 如果(汽车已从非高速公路顶点移动到高速公路顶点)或(汽车在上一步中收到等待信号):
        • if (\lfloor t / P_{\text{light}} \rfloor \mod 2) == 0: // 绿色交通灯
          • 参赛者的动作收到 OK 判决
          • 汽车驶入高速公路顶点
          • 下一步行动可以以标准方式决定
        • else: // 红色交通灯
          • x \leftarrow P_{\text{light}} - \left(t \mod P_{\text{light}}\right)
          • 参赛者的动作收到 WAIT x 判决
          • 汽车驶入高速公路顶点
          • 车辆需要在下一个赛道上停留在当前高速公路顶点 x 步骤
    • 注意:与其他事件不同,此事件是确定性的。

  • 所用概率分布的定义 可以在下面的详细信息部分找到。有关更多详细信息,请参阅随工具包分发的代码。

    定义: 概率分布
    • 在整个比赛中,我们使用三种类型的随机变量:(i) 指数分布随机变量,(ii) 幂律分布随机变量,以及 (iii) 幂律分布变量的逆随机变量。幂律分布变量有重尾并导致许多大的异常值。其逆值由幂律得出的随机变量有许多小的异常值。
    • 所有随机变量都定义在范围内 t \in [0,\infty).
    • 指数分布:
      • 参数: \mu (平均值)
      • 概率密度: p(t) = \frac{1}{\mu}\exp{\left(-\frac{t}{\mu}\right)}
      • 尾部概率: P(t \ge s) := \int_{s}^{\infty} p(t) \text{d}t = \exp{\left(-\frac{s}{\mu}\right)}
      • 交通拥堵持续时间是从此类分布中采样的。
    • 幂律分布
      • 参数: \epsilon (表征指数)和 \mathrm{median}
      • 导出的缩放参数: \mu = \frac{\mathrm{median}}{2^{\frac{1}{\epsilon}} - 1}
      • 概率密度: p(t)= \frac{\epsilon}{\mu}\left(1+\frac{t}{\mu}\right)^{-(1+\epsilon)}
      • 尾部概率: P(t \ge s) := \int_{s}^{\infty} p(t) \text{d}t = \left(1+\frac{s}{\mu}\right)^{-\epsilon}
      • 交通拥堵爆发延迟时间是从此类分布中采样的。
    • 具有幂律逆分布的随机变量。
      • 参数: \epsilon, \mathrm{median}
      • 变量 x:=1/t 是从幂律分布中采样的 p(x) 带参数 \epsilon, \mathrm{median}
      • 在算法中,我们对变量进行采样 x 来自幂律分布 \epsilon, \mathrm{median} 然后取其倒数得到所需的变量 t \leftarrow 1/x.
      • 汽车未损坏的持续时间以及客户取消的额外等待时间是从此类分布中采样的。

  • 评分

    • 比赛期间,提交的总分是通过对 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 点。

    问题C的详情:

    问题 C 是 互动 竞赛,其中参赛者代码连续接收来自主机代码的新生成和交付订单的更新,同时通过在每一步中将汽车移动到相邻位置来为客户提供服务 t=0,...,T_{\max}-1。此外,服务的规划算法必须掌握不断变化的情况,例如交通拥堵、汽车故障、订单取消和红绿灯。

    详细介绍了参赛者和主机代码交互的精确流程如下所示。

    参赛者代码 主机代码
    生成并输出图表 G
    新: 生成拥堵并输出潜在拥堵爆发时间 t_{i,d}
    + 新:时间 t: 广播汽车状态
    + 新:时间 t:广播交通状况
    + 新: 时间 t: 检查并输出已取消的订单
    + 时间 t:生成并输出新订单
    + 时间 t:如果在商店,则输出装载到汽车中的订单
    + 时间 t:确定并输出一步棋
    + 检查移动的可行性;如果移动不可行:输出 WA,如果可行:更新汽车位置, 新: 报告实际移动(如果在拥堵的高速公路上或在红色交通灯前,可能与请求的移动不同)
    + 时间 t+1:更新并输出已交付物品的信息(如果有)

    注意:主机代码仅输出一次图形、订单频率和交通拥堵信息。表左侧用“+”标记的过程对于整数迭代重复 t in t = 0,..., T_{\max} - 1.


    通过标准 IO 的交互式输入/输出格式

    初始化

    首先,主机代码将输出一个图表 G 和阶次频率 f_{i} 对于每个顶点 i,与订单出现在顶点的概率成正比 i。此外,时代 t_{d,i}, \cdots, t_{d,i} 沿途可能爆发交通拥堵 d,交通灯的切换周期 P_{\text{light}} 和总步数 提供了 T_{\max} 。

    |V| |E|
    u_1 v_1 d_{u_1, v_1} e_{u_1, v_1} e_{v_1, u_1}
    u_2 v_2 d_{u_2, v_2} e_{u_2, v_2} e_{v_2, u_2}
    \vdots
    u_{|E|} v_{|E|} d_{u_{|E|}, v_{|E|}} e_{u_{|E|}, v_{|E|}} e_{v_{|E|}, u_{|E|}}
    f_1 f_2 \ldots f_{|V|}
    t_{1,1}, \cdots, t_{1,4}
    \vdots
    t_{4,1}, \cdots, t_{4,4}
    P_{\text{light}}
    T_{\text{warning}}
    T_{\max}
    
    • 第一行: |V| 顶点数, |E| 边数
    • 下一个 |E| 线:图形的边缘。特别是, i第行表示顶点 u_i 和 v_i 形成一条边,以及相应的边权重 d_{u_i, v_i}。此外, e_{u_i, v_i} 和 e_{u_i, v_i} 表示沿边缘方向的街道类型 分别为 u_i \to v_i) 和 v_i \to u_i。特别是:
      • e_{u_i, v_i} = 0 :边缘方向 u_i \to v_i 连接两条标准道路。
      • e_{u_i, v_i} = d \in {1,2,3,4} :边缘方向 u_i \to v_i 是沿着高速公路方向 d.
      • e_{u_i, v_i} = 5 :边缘方向 u_i \to v_i 有其端点 v_i 在高速公路上。
      • e_{u_i, v_i} = 6 :边缘方向 u_i \to v_i 有其起始顶点 u_i 在高速公路上。
    • 下一行:订单频率 f_i 确定顶点处订单的概率 i as p_{i}=\frac{f_{i}}{\sum_{i}f_{i}}.
    • 接下来四行:每行 t_{d,1}, \cdots, t_{d,4} (d=1,\cdots,4) 表示四个时间点,此后沿方向可能会爆发新的交通拥堵 d.
    • 下一行:表示亮灯周期 P_{\text{light}}.
    • 下一行:表示句点 T_{\text{warning}},之后如果参赛者没有返回商店,汽车就会坏掉。
    • 最后一行:汽车位置更新总数 T_{\max}.

    交互式循环

    时间 t 我们首先通过标准输入获取以下信息。

    \mathrm{CAR\_STATUS}
    \mathrm{jam}_{1} \mathrm{jam}_{2} \mathrm{jam}_{3} \mathrm{jam}_{4}
    N_{\text{cancel}}
    \mathrm{cancel\_id}_1
    \mathrm{cancel\_id}_2
    \vdots
    \mathrm{cancel\_id}_{N_{\text{cancel}}}
    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
    \vdots
    \mathrm{put\_id}_{N_{\text{put}}}
    
    • 第一行代表 \mathrm{CAR\_STATUS} 可以采用以下值之一:
      • NOT_BROKEN :表示汽车状况良好。
      • WARNING t :表示汽车将闯入 t 步骤,如果不返回商店。
      • BROKEN :表示该车当前已损坏,无法在该步骤中移动。在这种情况下,参赛者应该输出 stay,即 -1 否则答案将变成 NG.
    • 二线沿高速公路方向广播交通状况 d=1,2,3,4。特别是,如果 \mathrm{jam}_d is 0,方向 d 没有交通堵塞。另一方面,如果 \mathrm{jam}_d is 1,方向 d 卡住。
    • 下一行: N_{\text{cancel}} 代表该时刻已取消的订单数量 t.
    • 后续 N_{\text{cancel}} 行表示已取消的订单。特别是, i第行表示订单ID为 \mathrm{cancel\_{id}}_i 已被取消。
    • 下一行: 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 必须是 w = u or w = v

    此外,如果 \mathrm{CAR\_STATUS} is BROKEN,参赛者需发送 -1 到标准输出。如果不这样做,将导致主机代码将移动判断为 NG,最终导致 WA,即错误答案,如下文进一步所述。

    参赛者动作后的时间 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(不正确)。如果您不立即终止,则行为未定义。
      • JAM :如果请求的沿卡住方向的移动被拒绝,则出现。 (注:沿已接受的卡住方向移动,将收到 OK,表示移动已按请求执行。)
      • WAIT t :表示请求的移动可行,并且汽车已相应移动。然而,由于赛车已从高速公路外移至高速公路顶点,因此现在要求参赛者在红绿灯处等待 t 步骤,即参赛者代码必须输出 -1 下一个 t 步骤。如果不这样做将导致判决 NG。进一步注意,当在绿色交通信号期间进入高速公路顶点时,主机代码将发送判决 OK.
    • 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
    • |V| = 625
    • 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|)
    • 0 \leq e_{u_i, v_i}, e_{v_i, u_i} \leq 6 (1 \leq i \leq |E|)
    • 给定的图没有自环,没有重边,并且保证是连通的。
    • f_1 = 0
    • f_i \in \left\{0, 1, 2 \right\} (2 \leq i \leq |V|)
    • 0 \leq t_{d,1} \leq t_{d,2} \leq t_{d,3} \leq t_{d,4} \lt T_{\text{max}} (1 \leq d \leq 4)
    • 50 \leq T_{\text{warning}} \leq 120
    • 10 \leq P_{\text{light}} \leq 30

    交互式循环

    • \mathrm{CAR\_STATUS} \in \{ NOT_BROKEN, WARNING t, BROKEN\}
    • \mathrm{jam}_{1}, \mathrm{jam}_{2}, \mathrm{jam}_{3}, \mathrm{jam}_{4} \in \{0,1\}
    • 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}})
    • 0 \leq N_{\text{cancel}} \leq T_{\text{last}}+1
    • 1 \leq \mathrm{cancel\_id}_{i} \leq T_{\text{last}}+1 (1 \leq i \leq N_{\text{cancel}}).
    • 0 \leq N_{\text{put}} \leq T_{\text{last}}+1
    • 1 \leq \mathrm{put\_id}_{i} \leq T_{\text{last}}+1 (1 \leq i \leq N_{\text{put}}).
    • 参赛者在某个时刻输出到标准输出的整数 t 必须是 -1 or 1 \leq w \leq |V|
    • \mathrm{verdict} \in \{OK, NG,JAM, WAIT t\}
    • 0 \leq N_{\text{achieve}} \leq T_{\text{last}}+1
    • 1 \leq \mathrm{achieve\_id}_{i} \leq T_{\text{last}}+1 (1 \leq i \leq N_{\text{achieve}}).

    输入/输出示例

    在此 IO 示例中,我们将使用下面可视化的情况。特别是:

    • 图表 :该示例显示了一个具有 16 个顶点和 18 条边的图。
    • 赛道 用黑色标记并具有以下说明。
      • d=1 : 3\to7\to11\to15
      • d=2 : 15\to11\to7\to3
      • d=3 : 9\to10\to11\to12
      • d=4 : 12\to11\to10\to9.
    • 从步骤 0 to 8 :汽车将交付带有 ID 的订单 1 到顶点 14,而顶点处的顺序 16 将过期。运送路线用红色箭头标记。台阶处出现交通拥堵 4\to5.
    • 从步骤 8 to 14 :汽车故障警告 将会出现 WARNING 5 并且汽车尝试返回商店顶点 1 进行修复。然而,顶点的红绿灯 9 将输出红色信号 WAIT 2 要求汽车等待两步 11, 12.
    • 步骤 13 汽车到达顶点对之间 1, 9 并中断,收到 BROKEN.
    • 步骤 14 :开车时无法朝商店移动 BROKEN 导致输出 NG.
    overview

    注意:由于教学原因,该示例已被缩小,并且不满足上面列出的约束。

    时间 参赛者 主机代码 说明
    16 18
    5 1 2 0 0
    2 3 2 5 6
    2 6 4 0 0
    3 4 2 6 5
    3 7 1 1 2
    4 8 4 0 0
    1 6 2 0 0
    1 9 2 5 6
    7 11 1 1 2
    9 10 1 3 4
    9 13 2 6 5
    9 14 2 6 5
    10 11 1 3 4
    11 12 1 3 4
    11 15 1 1 2
    12 16 2 6 5
    14 15 2 5 6
    15 16 2 6 5
    0 1 0 1 1 2 0 1 0 0 0 0 1 1 0 1
    3 167 311 913
    63 617 791 837
    325 473 893 915
    156 387 627 849
    6
    5
    10000
    
    主机代码通过标准输入提供初始化数据。
    第一行:该图有 |V| = 16 顶点和 |E| = 18 边缘。
    接下来的 18 行(第 2 - 19 行)表示图形的边缘。例如:
    第二行:表示顶点之间的边 5 和 1 由一条距离的街道连接 2。第四位数字 0 表示从 5\to1 是一条标准道路。最后一位数字 0 表示从 5\to 1 也是标准道路。
    第三行:表示顶点之间的边 2 和 3 由一条距离的街道连接 2。第四位数字 5 表示从 2\to3 通向高速公路。最后一位数字 6 表示从 3 \to 2 驶离高速公路。
    第6行:表示顶点之间的边 3 和 7 由一条距离的街道连接 1。第四位数字 1 表示从 3\to7 是一条高速公路 方向 1。最后一位数字 2 表示从 7\to3 是一条高速公路 方向 2.
    第 20 行:表示每个顶点的顺序频率。
    第21行:表示方向一潜在的交通拥堵爆发高峰。
    第22行:表示二号方向潜在的交通拥堵爆发高峰。
    第23行:表示方向三潜在的交通拥堵爆发高峰。
    第24行:表示四方向潜在的交通拥堵爆发高峰。
    25号线:红绿灯时段 P_{\text{light}}=6.
    第26行:表示汽车警告期 T_{\text{warning}}=5.
    第27行: T_{\max}=10000 。
    0 \rightarrow 1
    NOT_BROKEN
    0 0 0 0
    0
    1
    1 14
    1
    1
    
    时间 t=0 我们获悉: 第一行:我们的车是 NOT_BROKEN。 2号线:高速公路沿线不堵车。 第三行: 0 订单已被取消。 第四行:有 1 新订单。 第5行:新订单有ID 1 并应交付给顶点 14。 第六行:有 1 订单放入车内(因为我们在商店顶点)。 第7行:放入车的订单有ID 1.
    9
    
    参赛者向顶点移动一步 9.
    OK
    0
    
    第一行表明移动是可行的。第二行显示没有订单已交付。
    1 \rightarrow 2
    NOT_BROKEN
    0 0 0 0
    0
    1
    2 16
    0
    
    时间 t=1 我们获悉: 第一行:车是 NOT_BROKEN。 2号线:高速公路沿线不堵车。 第三行: 0 订单已被取消。 第四行:有 1 新订单。 第5行:新订单有ID 2 并应交付给顶点 16。 第六行:有 0 订单放入车内。 (汽车不在商店顶点。)
    9
    
    参赛者向顶点移动一步 9.
    OK
    0
    
    汽车在绿色交通灯时进入高速公路。因此,第一行表明此举是可行的。第二行显示没有订单已交付。
    2 \rightarrow 3
    NOT_BROKEN
    0 0 0 0
    0
    0
    0
    
    时间 t=2 我们获悉: 第一行:我们的车是 NOT_BROKEN。 2号线:高速公路沿线不堵车。 第三行: 0 订单已被取消。 第四行:有 0 新订单。 第五行:有 0 订单放入车内。
    10
    
    参赛者将车向顶点移动一步 10.
    OK
    0
    
    第一行表明移动是可行的。第二行显示没有订单已交付。
    3 \rightarrow 4
    NOT_BROKEN
    0 0 0 0
    0
    0
    0
    
    时间 t=3 我们获悉: 第一行:汽车是 NOT_BROKEN。 2号线:高速公路沿线不堵车。 第三行: 0 订单已被取消。 第四行:有 0 新订单。 第五行:有 0 订单放入车内。
    11
    
    参赛者决定向顶点迈出一步 11.
    OK
    0
    
    第一行表明移动是可行的。第二行显示没有订单已交付。
    4 \rightarrow 5
    NOT_BROKEN
    1 0 0 0
    0
    0
    0
    
    时间 t=4 我们获悉: 第一行:车是 NOT_BROKEN。 2号线:高速公路方向堵车 d=1。 第三行: 0 订单已被取消。 第四行:有 0 新订单。 第五行:有 0 订单放入车内。
    15
    
    参赛者尝试向顶点移动一步 15.
    JAM
    0
    
    第一行表示沿堵车方向行驶 d=1 被拒绝。汽车停留在顶点 11。第二行显示没有订单已交付。
    5 \rightarrow 6
    NOT_BROKEN
    1 0 0 0
    0
    0
    0
    
    时间 t=5 我们获悉: 第一行:汽车是 NOT_BROKEN。 2号线:高速公路方向堵车 d=1。 第三行: 0 订单已被取消。 第四行:有 0 新订单。 第五行:有 0 订单放入车内。
    15
    
    再次,参赛者尝试向顶点移动一步 15 (尽管这个方向有交通堵塞)。
    OK
    0
    
    第一行表示该举动已被接受(幸运!)。第二行显示没有订单已交付。
    6 \rightarrow 7
    NOT_BROKEN
    1 0 0 0
    0
    0
    0
    
    时间 t=6 我们获悉: 第一行:车是 NOT_BROKEN。 2号线:高速公路方向堵车 1。 第三行: 0 订单已被取消。 第四行:有 0 新订单。 第5行:有 0 订单放入车内。
    14
    
    小车向顶点移动一步 14.
    OK
    0
    
    第一行表明移动是可行的。第二行显示没有订单已交付。
    7 \rightarrow 8
    NOT_BROKEN
    0 0 0 0
    1
    2
    0
    0
    
    时间 t=7 我们获悉: 第一行:车是 NOT_BROKEN。 2号线:高速公路沿线不堵车。 第三行: 1 订单已被取消。 第4行:已取消订单的ID为 2。 第五行:有 0 新订单。 第六行:有 0 订单放入车内。
    14
    
    参赛者决定将车向顶点移动一步 14.
    OK
    1
    1
    
    第一行表明该移动是可行的。第二行表明 1 订单已交付。第三行显示带有ID的订单 1 已交付。
    8 \rightarrow 9
    WARNING 5
    0 0 0 0
    0
    0
    0
    
    时间 t=8 我们获悉: 第 1 行:汽车将在 5 步内刹车。 2号线:高速公路沿线不堵车。 第三行: 0 订单已被取消。 第四行:有 0 新订单。 第五行:有 0 订单放入车内。
    9
    
    参赛者将车移向顶点 9.
    OK
    0
    
    第一行表明移动是可行的。第二行显示没有订单已交付。
    9 \rightarrow 10
    WARNING 4
    0 0 0 0
    0
    0
    0
    
    时间 t=9 我们获悉: 第 1 行:汽车将分 4 步刹车。 2号线:高速公路沿线不堵车。 第三行: 0 订单已被取消。 第四行:有 0 新订单。 第五行:有 0 订单放入车内。
    9
    
    参赛者将车移向顶点 9.
    WAIT 2
    0
    
    第一行表明该移动是可行的。汽车现在位于高速公路顶点 9。但由于红绿灯的原因,选手现在需要在当前顶点等待两步。第二行显示没有订单已交付。
    10 \rightarrow 11
    WARNING 3
    0 0 0 0
    0
    0
    0
    
    时间 t=10 我们获悉: 第 1 行:汽车将分 3 步刹车。 2号线:高速公路沿线不堵车。 第三行: 0 订单已被取消。 第四行:有 0 新订单。 第五行:有 0 订单放入车内。
    -1
    
    汽车停留在顶点 9 等待红绿灯。 (如果不这样做将导致判决 NG.)
    WAIT 1
    0
    
    第一行表明该移动是可行的。汽车仍在高速公路顶点 9。另外,要求参赛者在当前顶点再等待一步。第二行显示没有订单已交付。
    11 \rightarrow 12
    WARNING 2
    0 0 0 0
    0
    0
    0
    
    时间 t=11 我们获悉: 第一行:汽车将分两步刹车。 2号线:高速公路沿线不堵车。 第三行: 0 订单已被取消。 第四行:有 0 新订单。 第五行:有 0 订单放入车内。
    -1
    
    汽车停留在顶点 9 等待红绿灯。 (如果不这样做将导致判决 NG.)
    OK
    0
    
    第一行表明移动是可行的。第二行显示没有订单已交付。
    12 \rightarrow 13
    WARNING 1
    0 0 0 0
    0
    0
    0
    
    时间 t=12 我们获悉: 第 1 行:汽车将在 1 步内刹车。 2号线:高速公路沿线不堵车。 第三行: 0 订单已被取消。 第四行:有 0 新订单。 第五行:有 0 订单放入车内。
    1
    
    汽车被指示向顶点移动一步 1。 (红绿灯等待时间已结束。)
    OK
    0
    
    第一行表明移动是可行的。第二行显示没有订单已交付。
    13 \rightarrow 14
    BROKEN
    0 0 0 0
    0
    0
    0
    
    时间 t=13 我们获悉: 第一行:车是 BROKEN。 (参赛者需输出 -1。) 2号线:高速公路沿线不堵车。 第三行: 0 订单已被取消。 第四行:有 0 新订单。 第五行:有 0 订单放入车内。
    1
    
    参赛者错误地决定向顶点移动一步 1.
    NG
    
    第一行表明该移动不可行。参赛者必须终止其节目。 (如果参赛者在上一步中返回到商店顶点,则 CAR_STATUS 将从 WARNING t to NOT_BROKEN.)

    使用标准输出

    将移动指令返回到标准输出时,请使用flush命令。作为示例,考虑您要输出的情况 -1。这是在一些主要编程语言中执行此操作的方法。

    C++

    std::cout << "-1" << std::endl;
    

    Java

    System.out.println("-1");
    

    Python 3.4

    print("-1", flush=True)
    

    示例代码 C

    通过以下方式提供了用于在本地参赛者环境中生成输入样本、评分和测试的软件工具包 链接。此外我们还提供 可视化软件 参赛者成绩。

    可视化器

    步骤
    FPS
    命令
    Δ
    分数