← 返回题目列表

Codeforces · 2217/F

F. 间隔游戏

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

Alice 和 Bob 正在玩一个涉及两个区间 $$$[l_1, r_1]$$$ 和 $$$[l_2, r_2]$$$ 的游戏,分别受整数 $$$x_1$$$ 和 $$$x_2$$$ 约束。区间满足 $$$1 \le l_1 \le r_1 \le x_1$$$ 和 $$$1 \le l_2 \le r_2 \le x_2$$$。

游戏玩法如下。在一个回合中,玩家必须选择两个间隔之一(假设第 $$$i$$$ 个间隔 $$$[l_i, r_i]$$$)并执行 正好一个 以下操作:

  • 将 $$$l_i$$$ 替换为严格较小的整数 $$$l'_i$$$,使得 $$$1 \le l'_i \lt l_i$$$。
  • 将 $$$r_i$$$ 替换为严格更大的整数 $$$r'_i$$$,使得 $$$r_i \lt r'_i \le x_i$$$。
无法做出有效动作的玩家输掉游戏。

游戏设置分两步进行:

  1. 首先,Alice 选择 $$$l_1$$$ 和 $$$r_1$$$ 的值来确定第一个区间。它必须是 $$$[1, x_1]$$$ 内的有效区间。
  2. 然后,选择第二个区间 $$$[l_2, r_2]$$$ 均匀随机 来自 $$$[1, x_2]$$$ 内所有可能的有效间隔。

一旦选择了时间间隔,游戏就会开始 爱丽丝先移动.

假设 Alice 和 Bob 都处于最佳状态,Alice 希望选择初始区间 $$$[l_1, r_1]$$$ 来最大化她获胜的概率。你的任务就是找到这样一个区间。如果有多个最佳区间,则可以输出其中任意一个。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的唯一行包含两个整数 $$$x_1$$$ 和 $$$x_2$$$ ($$$1 \le x_1, x_2 \le 5 \cdot 10^5$$$) - 两个区间的上限。

保证所有测试用例的 $$$x_1$$$ 总和不超过 $$$5 \cdot 10^5$$$。

保证所有测试用例的 $$$x_2$$$ 总和不超过 $$$5 \cdot 10^5$$$。

输出

对于每个测试用例,输出两个整数 $$$l_1$$$ 和 $$$r_1$$$ ($$$1 \le l_1 \le r_1 \le x_1$$$) – Alice 选择的最佳间隔。

如果有多个最佳间隔,则可以输出其中任意一个。

示例

输入
复制

6
1 1
1 10
2 1
2 2
20 64578
185367 133524

输出
复制

1 1
1 1
2 2
1 2
5 12
37381 52023

注意

对于第一个测试用例,Alice 被迫选择 $$$[1, 1]$$$,因为它是唯一有效的选项。

对于第三个测试用例,如果 Alice 选择 $$$[2, 2]$$$,她一定会赢(概率 $$$1$$$);她可以用 $$$1$$$ 替换 $$$l_1$$$,之后鲍勃就无法进行有效的移动。请注意,$$$[1, 1]$$$ 在这里也是有效的获胜答案。

对于第四个测试用例,如果 Alice 选择 $$$[1, 2]$$$,她的获胜概率为 $$$2/3$$$。相比之下,选择 $$$[1, 1]$$$ 或 $$$[2, 2]$$$ 的获胜概率仅为 $$$1/3$$$。