← 返回题目列表

Codeforces · 1811/D

D. 乌姆卡和长途飞行

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

女孩 Umka 喜欢旅行和参加数学奥林匹克竞赛。有一天,她乘飞机前往下一届奥运会,出于无聊,她翻阅了一张巨大的格子纸。

将第 $$$n$$$ 个斐波那契数表示为 $$$F_n = \begin{cases} 1, & n = 0; \\1,&n=1; \\ F_{n-2} + F_{n-1}, & n \ge 2. \end{案例}$$$

高度为 $$$F_n$$$ 且宽度为 $$$F_{n+1}$$$ 的方格矩形称为 $$$n$$$ 阶斐波那契矩形。

Umka 有一个 $$$n$$$ 阶的斐波那契矩形。有人在 $$$x$$$ 行和 $$$y$$$ 列的交叉处给一个单元格着色。

有必要将这个矩形精确地切割成 $$$n+1$$$ 正方形,这样

- 绘制的单元格位于边长为 $$$1$$$ 的正方形中;
- 最多有一对边长相等的正方形;
- 每个正方形的边长等于斐波那契数。

Umka 能用这种方式切割这个矩形吗?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^5$$$) — 测试用例的数量。

对于每个测试用例,给出整数 $$$n$$$、$$$x$$$、$$$y$$$($$$1 \le n \le 44$$$、$$$1 \le x \le F_n$$$、$$$1 \le y \le F_{n+1}$$$)——斐波那契矩形的阶数和彩色单元格的坐标。

输出

对于每个测试用例,如果答案是肯定的,则打印“YES”,否则打印“NO”。

在任何情况下都可以打印“YES”和“NO”(例如,字符串“yEs”、“yes”和“Yes”将被识别为肯定答案)。

示例

输入 #1

12
1 1 1
2 1 2
3 1 4
3 3 2
4 4 6
4 3 3
5 6 5
5 4 12
5 2 12
4 2 1
1 1 2
44 758465880 1277583853

输出 #1

YES
NO
YES
YES
YES
NO
YES
NO
NO
YES
YES
NO

注意

第一、第三和第四个测试用例。