luogu#P1915. [NOI2010] 成长快乐
[NOI2010] 成长快乐
题目描述
Nemo 是一条无忧无虑的小鱼,它的初始体重为 。可爱的 Nemo 希望自己能够尽快地成长,因此需要吃尽量多的食物。Nemo 最喜爱的食物是海里的小虾。
已知 Nemo 对食物的情况了解如下:大海里共有 只小虾,从 到 编号,其中编号为 的小虾的重量为 。将大海看作一个 X-Y 坐标系,在 时刻编号为 的小虾所在的位置为 。小虾在大海中作匀速直线运动,其中编号为 的小虾的速度向量为 ,即在时刻 ,它的位置为 。
Nemo 在 时刻的位置为 ,它可以在海中随意移动,但速度不超过 。Nemo 希望通过自己的努力,在 个单位时间内(含 时刻)吃到的小虾重量总和尽量大。
当 Nemo 与某只小虾同时移动到同一个位置上,且小虾的重量小于 Nemo 当时的重量,则 Nemo 可以将该小虾吃掉。当 Nemo 吃掉重量为 的小虾之后,它的体重将增加 。注意,小虾不会吃 Nemo,且小虾之间也不会自相残杀。
Nemo 希望你来帮助它制定一个成长计划,使得它吃掉的小虾重量总和尽量大。
输入格式
该题为提交答案型试题,所有输入数据 nemo1.in
nemo10.in
已在试题目录下。
对于每个数据,输入文件中第一行为五个实数 。分别表示 Nemo 的初始体重、最大移动速度、时间限制以及 Nemo 在 时刻的位置。
第二行为一个整数 ,表示大海中小虾的只数。
接下来 行,每行 个实数,包括 ,分别表示编号为 的小虾的重量、在 时刻的位置和速度向量。
输出格式
针对给定的 个输入文件 nemo1.in
nemo10.in
,你需要分别提交你的输出文件 nemo1.in
nemo10.in
。
输出文件第一行包含一个整数 。表示在你的成长计划中,Nemo 将吃到 只小虾。
第二行包含一个实数 ,表示在你的成长计划中,Nemo 吃到的小虾的重量总和。
接下来 行,每行 个数 。表示在时刻 ,Nemo 在位置 处吃掉了编号为 的小虾。其中 为实数, 为整数。
为保证验证程序的精度,所有实数建议至少输出到小数点后 位。在验证程序中,两个实数绝对误差不超过 时,即视为相等。
5 1 6 0 0
1
5 2 2 0 0
1
5
5 2 2 1
提示
样例解释
在这个样例中,Nemo 在时刻 在位置 吃掉了 号小虾。其实 Nemo 到达 的时间可以更早,但题中仅要求速度不超过 即可。
评分方法
对于每组数据,我们设置了 个评分参数 。如果选手的输出不合法,则得零分。否则,设在你的方案中,Nemo 体重的增加量为 ,你的分数将会由下表给出:
得分 | 条件 | 得分 | 条件 |
---|---|---|---|
10 | 5 | ||
9 | 4 | ||
8 | 3 | ||
7 | 2 | ||
6 | 1 |
checker 使用方法
在 checker 目录下,在终端输入 ./checker in out
。
其中 in 为题目提供的输入文件,out 为你对于该输入文件给出的答案文件。
校验器将只检查你的答案的合法性,结果以在线评测为准。
感谢 @FlierKing 提供 spj 以及 @虞皓翔 帮助完善 spj。