← 返回题目列表

AtCoder · stpc2025_2_j

J. KinGin 峰会

中文机器翻译题面 查看原题

配点 : 100 点

問題文

有一个无限广阔的二维格子。

在格子上有 N 个人,i 第 n 个人起初在 (R_{i} ,C_{i}) 每个人戴着金色或银色其中一种颜色的帽子。 i 第 n 个人在 H_i = G 时是金色,H_i = S 的时候戴着银色帽子。

1 每回合,各人可以根据帽子的颜色,从当前位置进行如下移动。

  • 戴金色帽子的人:
    可以停留在该格子,或者按照将棋中的金的移动方式移动。严格来说,可以将当前位置的格子移动到 (i, j) 转至 (i-1, j-1), (i-1, j), (i-1, j+1), (i, j-1), (i, j), (i, j+1), (i+1, j) 的任意一个。
  • 戴银色帽子的人:
    可以停留在该格子,或者按照将棋中的银的移动方式移动。严格来说,可以将当前位置的格子移动到 (i, j) 转至 (i-1, j-1), (i-1, j), (i-1, j+1), (i, j), (i+1, j-1), (i+1, j+1) 的任意一个。

N 请计算所有人聚集到同一格子所需的最少回合数。

T 会给出若干测试用例,请针对每个测试用例求出答案。

制約

  • T, N, R_i, C_i 是一个整数
  • 1 \le T \le 10^5
  • 1 \le N \le 2 \times 10^5
  • 1 \le R_i \le 10^9
  • 1 \le C_i \le 10^9
  • H_i 是 您也可以写 G 或 S 任何一个
  • 1 覆盖输入中的所有测试用例。 N 的总和是 2 \times 10^5 以下

部分点

附加限制 如果正确答案是满足 H_i = G 的数据集 给出 30 点。 如果您正确回答了所有满足


入力

输入按以下格式给出。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

在这里,\mathrm{case}_i 是 您也可以写 i 个测试用例。每个测试用例均按以下格式给出。

N
R_1 C_1 H_1
R_2 C_2 H_2
\vdots
R_N C_N H_N

出力

T 测试用例的答案,并用换行符分隔。 例如,通过按如下方式移动


入力例 1

5
2
2 1 G
4 4 S
3
2 1 G
2 4 G
2 2 S
2
3 2 G
3 2 S
1
3 4 G
10
2 4 S
2 3 G
10 8 S
7 3 S
2 6 S
7 1 S
9 1 G
5 2 S
7 8 G
2 1 S

出力例 1

2
2
0
0
5

1 测试用例,2 你们可以轮流聚集在同一个方格中。

  • 1 转 对
    • 人 1 是 您也可以写 (2, 2) 移至
    • 人 2 是 您也可以写 (3, 3) 移至
  • 2 转 对
    • 人 1 留在原地
    • 人 2 是 您也可以写 (2, 2) 移至

2 测试用例,2 你们可以轮流聚集在同一个方格中。

  • 1 转 对
    • 人 1 是 您也可以写 (1, 2) 移至
    • 人 2 是 您也可以写 (1, 3) 移至
    • 人 3 是 您也可以写 (1, 2) 移至
  • 2 转 对
    • 人 1 留在原地
    • 人 2 是 您也可以写 (1, 2) 移至
    • 人 3 留在原地

3 对于测试用例,大家从一开始就聚集在同一个广场上。


入力例 2

2
2
1 1 G
3 3 G
5
1 4 G
5 2 G
3 1 G
3 6 G
1 2 G

出力例 2

2
3

1 测试用例,2 你们可以轮流聚集在同一个方格中。

  • 1 转 对
    • 人 1 是 您也可以写 (2, 1) 移至
    • 人 2 是 您也可以写 (2, 2) 移至
  • 2 转 对
    • 人 1 留在原地
    • 人 2 是 您也可以写 (2, 1) 移至

这个输入示例满足部分分数的否定条件。