Cannonball

题目描述

Bessie 精通了把自己变成炮弹球并在一条长度为 $N$（$1 \leq N \leq 10^5$）的数轴上弹跳的技巧，数轴上的位置从左到右编号为 $1,2,\dots,N$。 她从某个整数位置 $S$（$1 \leq S \leq N$）开始，以初始力量 $1$ 向右弹跳。如果 Bessie 的力量为 $k$，那么她下一次弹跳会落在距离当前位置向前 $k$ 的位置。

从 $1$ 到 $N$ 的每个整数位置要么是靶子（target），要么是跳板（jump pad）。每个靶子和跳板都有一个范围在 $0$ 到 $N$（含）之间的整数值。 数值为 $v$ 的跳板会使 Bessie 的力量增加 $v$，并反转她的方向。数值为 $v$ 的靶子在 Bessie 以至少 $v$ 的力量落在其上时会被击破。落在靶子上不会改变 Bessie 的力量或方向。被击破的靶子会保持击破状态，Bessie 仍然可以落在上面，同样不会改变力量或方向。

如果 Bessie 无限弹跳，或者直到她离开数轴为止，她会击破多少个靶子？

如果 Bessie 起始位置是一个她能击破的靶子，她会立刻将其击破。类似地，如果 Bessie 起始位置是一个跳板，则在她第一次跳跃之前先应用该跳板的效果。

输入格式

第一行包含 $N$ 和 $S$，其中 $N$ 是数轴长度，$S$ 是 Bessie 的起始位置。 接下来 $N$ 行描述每个位置。第 $i$ 行包含整数 $q_i$ 和 $v_i$，其中当位置 $i$ 是跳板时 $q_i = 0$，当位置 $i$ 是靶子时 $q_i = 1$，并且 $v_i$ 是位置 $i$ 的数值。

输出格式

输出一个数字，表示将被击破的靶子数量。

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

1

6 4
0 3
1 1
1 2
1 1
0 1
1 1

3

提示

Bessie 从坐标 $2$ 开始，该处是一个数值为 $1$ 的靶子，因此她会立刻将其击破。然后她弹到坐标 $3$，该处是一个数值为 $2$ 的靶子，因此她无法击破。她继续到坐标 $4$，该处会切换她的方向并将她的力量增加 $1$ 到 $2$。她再弹回坐标 $2$，该处是一个已被击破的靶子，因此她继续。此时她会弹到坐标 $0$，因此停止。她恰好击破了一个位于 $2$ 的靶子。

Bessie 走过的路径为 $4\to 5\to 3\to 1\to 6$，下一次弹跳会使她离开数轴（到 $11$）。她按顺序击破了靶子 $4, 3, 6$。

SCORING: Inputs 3-5: $N \le 100$ Inputs 6-10: $N \le 1000$ Inputs 11-20: No additional constraints. Problem credits: Suhas Nagar

标签: USACO|2024|Bronze

来源

USACO|2024|Bronze