[蓝桥杯 2025 省 A] 红黑树

题目描述

有一棵无限大的完全二叉树（每个点都有左、右两个孩子）。每个点要么是红色，要么是黑色，颜色按下面这个规则定：

1. 根结点（第 1 行第 1 个）是 红色。
2. 如果一个点是红色，它的左孩子也是红色，右孩子是黑色。
3. 如果一个点是黑色，它的左孩子也是黑色，右孩子是红色。

现在会给出一些询问。每个询问给你两个数 (n, k)：表示第 (n) 行从左到右第 (k) 个点。 请你回答：这个点是 RED 还是 BLACK。

小提示（理解用）：从根走到第 (n) 行第 (k) 个点，一共走 (n-1) 步。每往右走一次就把颜色翻转一次（红↔黑），往左走不变色。也就是说，看"右走了几次"的奇偶性就行。

输入格式

• 第一行：一个整数 (m)，表示询问的次数。
• 接下来 (m) 行：每行两个整数 \(n_i, k_i\)，表示第 \(n_i\) 行第 \(k_i\) 个结点。

输出格式

• 输出 (m) 行，每行一个单词：

  • RED 代表红色
  • BLACK 代表黑色

输入输出样例 #1

输入 #1

2
1 1
2 2

输出 #1

RED
BLACK

说明/提示

• 样例解释：

  • 第 1 行第 1 个是根，规定为红色 → RED；
  • 第 2 行有两个点：从左到右第 2 个是右孩子，相比根向右走了一次，颜色翻转一次 → BLACK。

• 数据范围：

  • \(1 \le m \le 10\)
  • \(1 \le n_i \le 30\)
  • \(1 \le k_i \le 2^{n_i-1}\)