#P1915. [NOI2010] 成长快乐

    ID: 940 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>动态规划dp贪心2010NOI 系列提交答案Special Judge随机贪心随机化

[NOI2010] 成长快乐

题目描述

Nemo 是一条无忧无虑的小鱼,它的初始体重为 w0w_0。可爱的 Nemo 希望自己能够尽快地成长,因此需要吃尽量多的食物。Nemo 最喜爱的食物是海里的小虾。

已知 Nemo 对食物的情况了解如下:大海里共有 nn 只小虾,从 11nn 编号,其中编号为 ii 的小虾的重量为 wiw_i。将大海看作一个 X-Y 坐标系,在 00 时刻编号为 ii 的小虾所在的位置为 (xi,yi)(x_i, y_i)。小虾在大海中作匀速直线运动,其中编号为 ii 的小虾的速度向量为 (pi,qi)(p_i, q_i),即在时刻 tt,它的位置为 (xi+pit,yi+qit)(x_i+p_i \cdot t,y_i+q_i \cdot t)

Nemo 在 00 时刻的位置为 (x0,y0)(x_0, y_0),它可以在海中随意移动,但速度不超过 VV。Nemo 希望通过自己的努力,在 TT 个单位时间内(含 TT 时刻)吃到的小虾重量总和尽量大。

当 Nemo 与某只小虾同时移动到同一个位置上,且小虾的重量小于 Nemo 当时的重量,则 Nemo 可以将该小虾吃掉。当 Nemo 吃掉重量为 wiw_i 的小虾之后,它的体重将增加 wiw_i。注意,小虾不会吃 Nemo,且小虾之间也不会自相残杀。

Nemo 希望你来帮助它制定一个成长计划,使得它吃掉的小虾重量总和尽量大。

输入格式

该题为提交答案型试题,所有输入数据 nemo1.in \sim nemo10.in 已在试题目录下。

数据以及checker下载

对于每个数据,输入文件中第一行为五个实数 w0,V,T,x0,y0w_0, V, T, x_0, y_0。分别表示 Nemo 的初始体重、最大移动速度、时间限制以及 Nemo 在 00 时刻的位置。

第二行为一个整数 nn,表示大海中小虾的只数。

接下来 nn 行,每行 55 个实数,包括 wi,xi,yi,pi,qiw_i, x_i, y_i, p_i, q_i,分别表示编号为 ii 的小虾的重量、在 00 时刻的位置和速度向量。

输出格式

针对给定的 1010 个输入文件 nemo1.in \sim nemo10.in,你需要分别提交你的输出文件 nemo1.in \sim nemo10.in

输出文件第一行包含一个整数 kk。表示在你的成长计划中,Nemo 将吃到 kk 只小虾。

第二行包含一个实数 ww,表示在你的成长计划中,Nemo 吃到的小虾的重量总和。

接下来 kk 行,每行 44 个数 t,x,y,st, x, y, s。表示在时刻 tt,Nemo 在位置 (x,y)(x, y) 处吃掉了编号为 ss 的小虾。其中 t,x,yt, x, y 为实数,ss 为整数。

为保证验证程序的精度,所有实数建议至少输出到小数点后 66 位。在验证程序中,两个实数绝对误差不超过 10410^{-4} 时,即视为相等。

5 1 6 0 0
1
5 2 2 0 0
1
5
5 2 2 1

提示

样例解释

在这个样例中,Nemo 在时刻 55 在位置 (2,2)(2, 2) 吃掉了 11 号小虾。其实 Nemo 到达 (2,2)(2, 2) 的时间可以更早,但题中仅要求速度不超过 VV 即可。

评分方法

对于每组数据,我们设置了 99 个评分参数 a10,a9,,a2a_{10},a_9, \ldots ,a_2。如果选手的输出不合法,则得零分。否则,设在你的方案中,Nemo 体重的增加量为 wuserw_{user},你的分数将会由下表给出:

得分 条件 得分 条件
10 wusera10w_{user} \geq a_{10} 5 wusera5w_{user} \geq a_5
9 wusera9w_{user} \geq a_9 4 wusera4w_{user} \geq a_4
8 wusera8w_{user} \geq a_8 3 wusera3w_{user} \geq a_3
7 wusera7w_{user} \geq a_7 2 wusera2w_{user} \geq a_2
6 wusera6w_{user} \geq a_6 1 wuser>0w_{user} \gt 0

checker 使用方法

在 checker 目录下,在终端输入 ./checker in out

其中 in 为题目提供的输入文件,out 为你对于该输入文件给出的答案文件。

校验器将只检查你的答案的合法性,结果以在线评测为准。

感谢 @FlierKing 提供 spj 以及 @虞皓翔 帮助完善 spj。