#P2394. 穿云箭[废题]
穿云箭[废题]
题目描述
风行者的技能“穿云箭”可以沿一条直线穿透多个小兵。风行者现在只能射出一箭,希望获得尽可能多的金币。
平面上有 个小兵。第 个小兵的位置为 ,当前生命值为 ,击杀它可以获得 枚金币。
风行者可以在平面上的任意位置射出一支箭,并任意选择射击方向。箭沿射击方向形成一条无限长的射线;只有位于该射线上的小兵才会中箭。小兵按照箭前进方向上的位置顺序依次中箭。
-
第一个中箭的小兵受到 点伤害。
-
对于第 个中箭的小兵(),它受到的伤害为
即每穿过一个小兵,后续伤害都变为前一次的 。
-
无论此前的小兵是否被击杀,只要中箭,就会使后续伤害衰减一次。
-
若某小兵中箭后剩余生命值 ,则认为它被击杀,可以获得 枚金币。金币只计算一次。
保证任意两个小兵的位置不同。 因此,同一射线上各小兵的中箭顺序确定。允许生命值、金币数或初始伤害为 ;当小兵生命值为 时,只要中箭,仍按上述条件判定为被击杀。
求风行者只射出一箭最多可以获得多少枚金币。允许选择不命中任何小兵,此时获得 枚金币。
输入格式
第一行包含三个整数 。
接下来 行,每行包含四个整数 ,分别表示第 个小兵的坐标、生命值以及击杀获得的金币。
输出格式
输出一个整数,表示一箭能够获得的最多金币数。
样例 1
输入
1 1 1
1 1 1 1
输出
1
样例 2
输入
6 2 1
2 2 1 1
1 1 1 1
3 3 1 1
1 3 1 1
1 2 1 1
3 1 1 1
输出
3
说明
从 之前向 的方向射击,可以依次命中 、、 三个小兵。它们依次受到 、 和 点伤害,均能够被击杀,共获得 枚金币。
数据范围与约定
- ;
- ;
- ;
- ;
- 任意两个小兵的坐标互不相同。
数据分布参考原题:约 的测试数据满足 ;约 的测试数据满足 。本修订版测试数据主要按边界与算法正确性设计,并不以这些比例构造评分子任务。