考虑平面上整数点中的多个位置。其中一个地点是工人们等待的基地。其他每个位置都包含一份工作。
每项工作都有以下特征:工作持续时间、所需工人数量、以及最早开始工作的时刻和最晚完成工作的时刻。为了完成这项工作,所需数量的工人必须同时开始工作,然后在工作期间持续出现在该地点。每项工作必须完全完成一次,或者保持不变。
我们的任务是确定工人应该做什么,以便我们获得更多利润。任何工人都可以为任何工作做出贡献。我们可以使用任意数量的工人,但每个工人必须至少参与一项工作。
每个工人在某个时刻从基地出发,然后在不同地点之间移动并完成工作,最后回到基地并完全停止。工人可以沿着坐标轴移动,并花费一分钟将其任何一个坐标增加或减少$$$1$$$。我们必须向工人支付 $$$240$$$ 积分以使其出现在我们的解决方案中,并且每分钟额外支付 $$$1$$$ 积分,直到工人完全停止为止。
我们完成的每项工作都会得到奖励。对于持续时间 $$$d$$$ 且所需工人数量 $$$p$$$ 的工作,我们获得 $$$d \cdot p \cdot (p + 5)$$$ 积分的奖励。未完成的工作不计入该金额。
输入
第一行包含从 $$$500$$$ 到 $$$2000$$$ 的整数 $$$n$$$:位置数。以下 $$$n$$$ 行中的每一行包含六个整数,并以 $$$x$$$ $$$y$$$ $$$d$$$ $$$p$$$ $$$l$$$ $$$h$$$ 格式描述一个位置。坐标 $$$x$$$ 和 $$$y$$$ 是从 $$$0$$$ 到 $$$100$$$ 的整数。持续时间 $$$d$$$ 是从 $$$5$$$ 到 $$$30$$$ 分钟的整数。所需工人数量 $$$p$$$ 是从 $$$1$$$ 到 $$$7$$$ 人的整数。最早可能的开始时刻$$$l$$$和最晚可能的完成时刻$$$h$$$是从$$$200$$$到$$$800$$$分钟的整数,选择使得$$$60 \le h - l \le 300$$$。
第一个位置是基地。它是上述规则的排除项,格式为 $$$x$$$ $$$y$$$ $$$0$$$ $$$0$$$ $$$0$$$ $$$0$$$。所有给定点 $$$(x, y)$$$ 都是不同的。
在所有测试中,数字 $$$n$$$ 以及所有分数、持续时间、所需工人数量和时间跨度都是从可用选项中随机、独立且统一地选择的。
输出
将每个工人的指令打印为几行块,如下所示:
- 开始(此时)(位置)块的第一行。确定工人从基地开始的时刻。该位置必须是基地,因此数字为 $$$1$$$。
- 到达(此时)(在位置)我们希望工作人员此时到达此位置。如果在上一个命令之后他不能及时完成,则该解决方案被认为是错误的。位置按输入顺序从 $$$1$$$ 到 $$$n$$$ 编号。
- 工作(开始时刻)(结束时刻)(地点)我们希望工作人员在这个确切的时间间隔内在此地点完成工作。该位置必须与前一个到达命令中的位置相同。如果工作人员在上一个命令之后无法及时到达,或者给定的时间间隔长度错误或超出了该位置的时间跨度,则该解决方案被认为是错误的。该命令必须在每个块中至少出现一次。请记住,每项工作必须由所需数量的工人同时完成,或者保持不变,否则解决方案将被视为不正确。
- end 块的最后一行。工人必须处于他开始时的同一位置。
在每个时刻,每个位置可能有任意多个工人。输出中的所有矩必须是从 $$$0$$$ 到 $$$1000$$$ 的整数,并且所有位置编号必须是从 $$$1$$$ 到 $$$n$$$ 的整数。
一个接一个地打印连续的块,没有间隙。
示例
说明
地点 $$$2$$$ 的工作奖励为 $$$30 \cdot 2 \cdot (2 + 5) = 420$$$ 积分。
地点 $$$3$$$ 的工作奖励为 $$$29 \cdot 1 \cdot (1 + 5) = 174$$$ 积分。
位置$$$4$$$ 的作业未完成。
我们必须向第一个工人支付 $$$240 + 71 = 311$$$ 积分。
我们还必须向第二个工人支付 $$$240 + 40 = 280$$$ 积分。
利润:$$$420 + 174 - 311 - 280 = 3$$$。
请注意,此示例太短($$$n < 500$$$),因此不会出现在测试系统中。包含它仅用于解释目的。
评分
每个测试都是独立评分的。测试分数是利润除以 $$$1000$$$。如果利润为负,则得分为零。如果解决方案在某个测试中未输出有效答案,则该测试的结果也为零。
测试
您的解决方案将根据预先生成的测试集进行检查。解决方案的分数是其所有测试结果的总和。如果解决方案在某个测试中未输出有效答案,则该测试的结果为零。
在比赛的主要阶段,有两种方式提交解决方案。
- 第一个,问题 A1,是检查示例。有 $$$10$$$ 示例测试也可用于本地测试。检查解决方案后,您可以通过单击提交结果来查看所有示例的报告。 A1 的测试已开放,您可以从链接 https://assets.codeforces.com/rounds/1160/codeforces-vrt-2019.tar.gz(适用于 Linux)和 https://assets.codeforces.com/rounds/1160/codeforces-vrt-2019.zip(适用于 Windows)下载它们。测试后,您可以单击提交的结论来查看每个测试的结果。
- 第二种方法,问题 A2,是检查初步测试。有 $$$100$$$ 预先生成但保密的初步测试。初步测试(但不包括示例测试)的分数用于初步记分板。该分数不会影响最终结果,但仍然可以将解决方案与其他解决方案进行粗略比较。
主阶段结束后,系统为每个参与者选择最终的解决方案:
- 考虑发送用于初步测试的所有解决方案;
- 选择总分严格大于零的;
- 将最终解决方案定义为所选解决方案中提交时间最晚的解决方案之一。
请注意,在选择最终解决方案时,不会考虑仅发送用于示例检查的解决方案。
在最终测试期间,所有最终解决方案都将在同一组大量($$$\大约 1000$$$)最终测试中进行检查。最终测试的分数决定了最终的记分板。获胜者是解决方案获得最高总分的参赛者。如果两名或两名以上参赛者总成绩相同,则得分相同的选手并列名次。