这是一个交互式优化问题。每个解决方案都将根据其效率获得分数,而不是必须找到最佳答案。由于问题是交互式的,在测试过程中,陪审团程序和您的解决方案将通过标准输入和输出流交换消息。打印消息后,记得刷新输出缓冲区以确保消息已完全发送。例如,您可以在 C++ 中使用 fflush(stdout)、Java 中使用 System.out.flush()、Pascal 中使用 flash(output) 以及 Python 中使用 stdout.flush()。
您的任务是实现下一代出租车服务 BuberPool 的自动化。每辆布伯车一次最多可运送四名乘客。汽车必须行驶到乘客所在的位置,接载他们并将他们送到目的地。此外,与传统出租车不同的是,每辆车最多可以同时处理四个订单。例如,当载客前往目的地时,汽车可以搭载额外的乘客,或者绕道送另一名乘客。
我们将使用以下简化的离散模型来解决这个现实问题。
将城市视为由 $$$w$$$ 街道和 $$$h$$$ 大道组成的矩形网格,以及 $$$w \times h$$$ 十字路口。街道编号从 $$$1$$$ 到 $$$w$$$,大道编号从 $$$1$$$ 到 $$$h$$$。我们将考虑时间的非负整数矩。操作以滴答为单位执行:连续时刻之间的时间间隔。在任何时刻,每辆车都位于某个十字路口$$$(x, y)$$$,其中$$$1 \le x \le w$$$ 和$$$1 \le y \le h$$$。任意数量的汽车可以同时位于同一个十字路口。在一个周期内,每辆车可以保持在同一个十字路口,也可以将其坐标之一(街道或大道)精确地改变一个。
在 $$$0$$$ 时刻,您将获得 $$$k$$$ 汽车的起始位置:$$$(x_1, y_1)$$$, $$$(x_2, y_2)$$$, $$$\ldots$$$, $$$(x_k, y_k)$$$。汽车数量等于 $$$k$$$ 并且在模拟过程中不会改变。
此外,您的解决方案将按照客户的订单提供。在这个问题中,每个订单都是由一名乘客发出的,因此一辆车最多可以同时处理四个订单。为了进一步简化问题,订单的时刻都是不同的,并且订单按时间顺序给出。因此,每个 $$$j$$$ 订单由五个整数描述:时刻 $$$t_j$$$、上车位置 $$$(sx_j, sy_j)$$$ 和下车位置 $$$(tx_j, ty_j)$$$。
在 $$$0$$$ 上勾选,并且在收到每个订单后,您可以向汽车驾驶员提供指令集。每次您都可以向任意数量的汽车提供指令集(稍后将详细介绍限制)。不同汽车的指令集是单独给出的。指令集是三元组 $$$(cx_1, cy_1, a_1)$$$、$$$(cx_2, cy_2, a_2)$$$、$$$\ldots$$$、$$$(cx_m, cy_m, a_m)$$$ 的序列,其中 $$$m$$$ 是指令集中的指令数。这些数字的含义如下:
- 汽车应首先行驶至 $$$(cx_1, cy_1)$$$,然后行驶至 $$$(cx_2, cy_2)$$$、$$$\ldots$$$,最后行驶至 $$$(cx_m, cy_m)$$$。每个位置 $$$(cx_i, cy_i)$$$ 可以是城市中的任何十字路口,不一定是上车或下车位置。当汽车从一个位置行驶到另一个位置时,汽车总是首先更改其第一个坐标,直到它等于目的地的第一个坐标,然后才更改第二个坐标。这样,当从 $$$(p_1, q_1)$$$ 行驶到 $$$(p_2, q_2)$$$ 时,汽车将首先移动 $$$(p_1, q_1) \rightarrow (p_2, q_1)$$$,然后 $$$(p_2, q_1) \rightarrow (p_2, q_2)$$$。在移动过程中的每一刻,汽车都会将其坐标精确地改变一个。
- 值 $$$a_i$$$ 编码动作。如果$$$a_i = 0$$$,则汽车只会行驶到$$$(cx_i, cy_i)$$$,并且不会执行任何特殊操作。如果$$$a_i > 0$$$,汽车行驶至$$$(cx_i, cy_i)$$$并在那里接载编号为$$$a_i$$$的乘客(乘客的上车位置应等于$$$(cx_i, cy_i)$$$,并且乘客仍应在那里等候)。如果 $$$a_i < 0$$$,则车厢移动到 $$$(cx_i, cy_i)$$$ 并下车编号为 $$$-a_i$$$ 的乘客(乘客的下车位置应等于 $$$(cx_i, cy_i)$$$,且乘客应在该车厢内)。接送乘客是即时的。
当您向汽车提供指令集时,其先前的指令集将被新的指令集替换。这样,一辆车一次最多只能执行一个指令集。如果没有任何指示,或者所有指示都已完成,则汽车将在最后的位置等待。指令按照给定的顺序执行。
For each order, first, all the cars perform their current instruction sets until the moment of the order comes, then the order is given to your program, and after that, your program prints new instruction sets for some of the cars.没有获得新指令集的汽车继续执行旧指令集。
因此,总体测试策略如下所示:
1. 您的解决方案读取城市尺寸、汽车数量及其初始坐标。
2. 该解决方案打印一些汽车的指令集,并且汽车开始执行指令。
3.解决方案读取一个整数$$$t_j$$$,下一个订单的时刻(如果$$$t_j = -1$$$,你的程序应该打印最终的指令集并正常退出)。
4. 该解决方案读取整数 $$$sx_j$$$、$$$sy_j$$$、$$$tx_j$$$、$$$ty_j$$$,即第 $$$j$$$ 个订单的取货和还车位置。
5. 该解决方案打印汽车的下一个指令集。
6. 转到步骤 3。
当你的程序在第3步退出后,首先所有的指令都会被完全执行,然后模拟才会结束。
您的解决方案在测试中获得的分数是所有订单的平均分数,四舍五入到最接近的整数。订单的得分等于 $$$\alpha \cdot (100 + w_0)$$$,其中 $$$w_0$$$ 是订单在理想情况下所需的时间,即从 $$$(sx_j, sy_j)$$$ 到 $$$(tx_j, ty_j)$$$ 的时间(因此,$$$w_0 = |sx_j - tx_j| + |sy_j - ty_j|$$$),$$$\alpha$$$ 是 $$$0$$$ 和 $$$1$$$ 之间的实际值,表征乘客对乘坐的满意度。值 $$$\alpha$$$ 通过以下公式计算:
$$$$$$\alpha = \frac{10^7 - 分钟(d_1^2 + d_2^2, 10^7)}{10^7}\text{,}$$$$$$
其中$$$d_1$$$是取货前的等待时间(下单时间与取货时间之间的滴答数),$$$d_2$$$是实际行程时间与理想行程时间之间的差值(理想行程时间为$$$w_0$$$)。如果订单未完成,$$$\alpha = 0$$$。
您的解决方案获得的分数只是每个测试的分数总和。
输入
输入的第一行包含整数 $$$w$$$ 和 $$$h$$$ ($$$300 \le w, h \le 3000$$$),即矩形城市的尺寸。第二行包含一个整数 $$$k$$$ ($$$1 \le k \le 40$$$),即汽车数量。接下来的 $$$k$$$ 行包含整数坐标 $$$x_i$$$ 和 $$$y_i$$$ ($$$1 \le x_i \le w$$$, $$$1 \le y_i \le h$$$),即汽车的初始位置。回想一下,任意数量的汽车都可以共享同一位置。
读取此数据后,您的程序应输出汽车的初始指令集(请参阅输出格式),然后处理订单。
每个订单都在其自己的行上给出,并由五个整数描述 $$$t_j$$$, $$$sx_j$$$, $$$sy_j$$$, $$$tx_j$$$, $$$ty_j$$$ ($$$1 \le t_j \le 86\,400$$$, $$$1 \le sx_j, tx_j \le w$$$, $$$1 \le sy_j, ty_j \le h$$$),其中 $$$t_j$$$ 是下单时刻,$$$(sx_j, sy_j)$$$ 是乘客的上车地点,$$$(tx_j, ty_j)$$$ 是乘客的下车地点。订单按严格递增 $$$t_j$$$ 排序。每个订单的上车和还车地点都不同。
在所有命令之后,您的程序将得到一行包含五个整数 $$$-1$$$ 的行。也就是说,如果读到另一笔订单后,$$$t_j = -1$$$,则表示已经没有订单了。保证订单数量在$$$1$$$到$$$500$$$之间。
阅读每份订单后,打印汽车的说明书。另外,在到达具有五个整数 $$$-1$$$ 的行后打印指令集。因此,如果输入包含 $$$q$$$ 订单,则打印汽车指令集的次数为 $$$q + 2$$$(第一个,每个订单后一个,最后一个)。
Remember that simulation is implemented in such a way that, for each order, first, all the cars perform their current instruction sets until the moment of the order comes, then the order is given to your program, and after that, your program prints new instruction sets for some of the cars.没有获得新指令集的汽车继续执行旧指令集。
在比赛的主要部分期间,您的解决方案将在 40 次测试的初步测试集上进行测试。其中一半测试(奇数测试)可通过以下网址下载:https://assets.codeforces.com/rounds/927/tests.zip。在已发布的测试中,陪审团准备的每种生成方法都会生成一个测试。
本轮结束后,将使用在初步测试中得分为正的最后一个解决方案进行测试。其他解决方案将被忽略。所有选定的解决方案都将在秘密测试集上进行测试,该测试集的生成方式与初步测试相同(相同的生成方法)。评审团将尽量保存测试类型,并且不要大量更改统计参数。
输出
您的解决方案的输出是汽车的指令集。仔细阅读问题陈述和输入格式以了解模拟过程。您打印的每条 $$$q + 2$$$ 消息都应该是单行上的整数序列。
Each message starts with a number $$$f$$$ ($$$0 \le f \le k$$$), that number of cars that will receive new instructions.它后面应该是 $$$f$$$ 空格分隔的块。
每个块对应于单个汽车的指令集。一个块以一对整数 $$$c$$$ 和 $$$m$$$ ($$$1 \le c \le k$$$)、汽车的编号和该汽车的指令序列的长度开始。接下来应该是 $$$m$$$ 指令:整数三元组 $$$cx, cy, a$$$ ($$$1 \le cx \le w$$$, $$$1 \le cy \le h$$$, $$$-q \le a \le q$$$),其中三元组意味着汽车应该行驶到位置 $$$(cx, cy)$$$ 并执行操作 $$$a$$$ (阅读声明)。这里,$$$q$$$ 是迄今为止收到的订单数。
程序的所有输出中的指令不应超过 $$$10^6$$$。
在打印指令集之后,但在等待下一个输入之前,请记住刷新输出缓冲区以确保消息已完全发送。例如,您可以在 C++ 中使用 fflush(stdout)、Java 中使用 System.out.flush()、Pascal 中使用 flash(output) 以及 Python 中使用 stdout.flush()。