问题陈述
20015年,JAG(Jagan Acceleration Group)成功发明了一种名为“Force Point”的新型加速器,用于二维$xy$平面上的质子碰撞实验。 如果质子接触力点,它会加速到其速度的两倍,并且其运动方向会发生转向。 质子可以通过力场以四种方式转向:平行于 $x$ 轴或 $y$ 轴的正方向或负方向。质子转向的方向由力点的类型决定。 力点只能加速质子一次,因为力点在加速后立即消失。 在二维平面上生成许多力点(称为 2D 力点场),使我们能够通过使用 2D 力点场中的力点顺序加速质子,将质子加速到目标速度。
Force Point 生成方法仍在试验中,JAG 具有以下技术限制:
- JAG 无法生成具有指定位置和类型的力点。
- 将质子放入 2D 力点场后,JAG 无法生成力点。
- JAG 无法移动原力点。
- JAG 无法改变质子的方向,除非通过力点的效果。
- JAG 只能将一个质子用于 2D 力点场。
- JAG 可以将质子以任意方向移动,速度为 1,置于 2D 力点场中的任意位置。
为了达到质子的最大速度,JAG的工程师必须在仔细观察生成的二维力点场后,选择质子的最佳初始位置和最佳初始方向,以便质子被尽可能多的力点加速。
通过观察生成的2D力点场,已知生成的力点的数量为$n$。第 $i$ 个点的位置 ($x_i$, $y_i$) 和方向转向类型 $d_i$ 也是已知的。 您的任务是编写一个程序,通过 JAG 最佳放置质子时在给定 2D 力点场上的加速度来计算质子的最大速度。
输入
输入由单个测试用例组成,该测试用例按以下格式描述 2D 力点字段。
$n$
$x_1$ $y_1$ $d_1$
...
$x_n$ $y_n$ $d_n$
第一行包含一个整数 $n$ ($1\le n\le 3{,}000$),它是 2D 力点场上力点的数量。接下来的 $n$ 行中的每一行都包含两个整数 $x_i$ 和 $y_i$ ($|x_i|, |y_i| \le 10^9$) 和一个字符 $d_i$ ($d_i$ 是 '>'、'v'、'<' 或 '^' 之一)。 $x_i$和$y_i$表示第$i$个力点的坐标,$d_i$是第$i$个力点的方向转向类型。类型为 '>' 的力点将质子的方向更改为 $x$ 轴的正方向,'v' 表示 $y$ 轴的正方向,'<' 表示 $x$ 轴的负方向,'^' 表示 $y$ 轴的负方向。您可以假设任意两个力点不是在同一坐标上生成的。
输出
显示包含整数 $\log_2 v_{\mathrm{max}}$ 的行,其中 $v_{\mathrm{max}}$ 是质子可能的最快速度。
示例输入 1
9 0 0 v 1 0 > 2 0 < 0 1 > 1 1 v 2 1 v 0 2 ^ 1 2 ^ 2 2 <
样本输入 1 的输出
9
输入如下图所示。 如果将质子放在 $(1, 1)$ 处,所有力点都会消失。
v>< >vv ^^<
示例输入 2
9 0 0 ^ 1 0 ^ 2 0 ^ 0 1 < 1 1 ^ 2 1 > 0 2 v 1 2 v 2 2 v
样本输入 2 的输出
2