#P12656. [KOI 2023 Round 1] 道具获取
[KOI 2023 Round 1] 道具获取
题目背景
试题来源:https://koi.or.kr/archives/。中文翻译做了少量本土化修改。
按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。
题目描述
你正在开发一款游戏,玩家将在二维地图中驾驶汽车收集道具。
地图上有 个可以获取道具的箱子。第 个箱子的位置是 ,每当汽车经过这个位置时,可以获得 个道具。
汽车只能沿与 x 轴或 y 轴平行的方向移动。汽车的每次移动通过两个整数 和 来表示:
- 若 ,表示 x 坐标增加 ;
- 若 ,表示 y 坐标增加 ;
- 若 ,表示 x 坐标减少 ;
- 若 ,表示 y 坐标减少 。
此时,位于起点位置的箱子不能获取道具。换句话说,如果汽车从 移动到 ,则不能获取 位置的箱子的道具,但可以获取 位置的箱子的道具。
汽车从 开始,接下来会移动 次。给出汽车的移动方向和距离,计算 次移动过程中能够获得的道具总数。
输入格式
第一行包含两个用空格分隔的整数 和 ,分别表示箱子的数量和汽车的移动次数。
接下来的 行中,每行包含三个整数 、、,表示第 个箱子的位置在 ,且经过该位置可以获得 个道具。
接下来的 行中,每行包含两个整数 、,表示汽车向方向 移动距离 。
输出格式
输出一行,表示 次移动过程中能获得的道具总数。
4 6
5 5 3
5 8 5
3 5 2
1 5 1
0 4
1 9
3 5
2 3
2 1
0 5
24
3 3
1 3 1
2 2 1
3 1 1
1 3
0 2
3 3
2
提示
样例 1 说明
如图所示,每次移动都会获得绿色标记的物品。
限制条件
- 所有输入数值均为整数。
- 所有箱子的位置彼此不同。
- 汽车在任意时刻的 x、y 坐标都在 范围内。
子问题
- (9 分),,,,,汽车所有时刻的坐标
- (17 分),,
- (15 分)所有箱子的 x 坐标互不相同,且 y 坐标也互不相同。
- (37 分)所有
- (22 分)无额外限制。
翻译由 ChatGPT-4o 完成