← 返回题目列表

Codeforces · 1623/B

B. 靶场游戏

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

Alice 和 Bob 玩以下游戏。 Alice 有一组不相交的整数范围 $$$S$$$,最初仅包含一个范围 $$$[1, n]$$$。一轮中,Alice 从集合 $$$S$$$ 中选择一个范围 $$$[l, r]$$$,并要求 Bob 在该范围内选择一个数字。 Bob 选择一个数字 $$$d$$$ ($$$l \le d \le r$$$)。然后,Alice 从 $$$S$$$ 中删除 $$$[l, r]$$$ 并将范围 $$$[l, d - 1]$$$ (如果 $$$l \le d - 1$$$)和范围 $$$[d + 1, r]$$$ (如果 $$$d + 1 \le r$$$)放入集合 $$$S$$$ 中。当集合 $$$S$$$ 为空时游戏结束。我们可以证明每场比赛的回合数恰好是 $$$n$$$。

玩完游戏后,Alice 记住了她从 $$$S$$$ 集合中选择的所有范围 $$$[l, r]$$$,但 Bob 不记得他选择的任何数字。但鲍勃很聪明,他知道他可以从爱丽丝的范围中找出他的数字$$$d$$$,因此他向你寻求编程技巧方面的帮助。

给定 Alice 选择的范围列表 ($$$[l, r]$$$),对于每个范围,帮助 Bob 找到 Bob 选择的数字 $$$d$$$。

我们可以证明,鲍勃总是有一种独特的方式来为爱丽丝选择的有效范围列表选择他的号码。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 1000$$$)。

接下来的 $$$n$$$ 行包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le n$$$),表示 Alice 在某个时刻选择的范围 $$$[l, r]$$$。

请注意,范围没有按特定顺序给出。

保证所有测试用例的$$$n$$$总和不超过$$$1000$$$,并且每个测试用例的范围来自有效的游戏。

输出

对于每个测试用例打印 $$$n$$$ 行。每行应包含三个整数 $$$l$$$、$$$r$$$ 和 $$$d$$$,表示对于 Alice 的范围 $$$[l, r]$$$ Bob 选择了数字 $$$d$$$。

您可以按任意顺序打印行。我们可以证明答案是唯一的。

不需要在每个测试用例之后打印新行。示例输出中的新行仅供阅读。

示例

输入 #1

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

输出 #1

1 1 1

1 3 1
2 2 2
2 3 3

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

1 5 3
1 2 1
4 5 5
2 2 2
4 4 4

注意

在第一个测试用例中,只有 1 个范围 $$$[1, 1]$$$。 Alice 只能选择一个范围 $$$[1, 1]$$$,Bob 只能选择一个数字 $$$1$$$。

在第二个测试用例中,$$$n = 3$$$。最初,该集合仅包含一个范围 $$$[1, 3]$$$。

- Alice 选择了范围 $$$[1, 3]$$$。鲍勃选择了号码 $$$1$$$。然后,Alice 将范围 $$$[2, 3]$$$ 放回到集合中,在本轮之后,它是集合中唯一的范围。
- Alice 选择了范围 $$$[2, 3]$$$。鲍勃选择了数字$$$3$$$。然后 Alice 将范围 $$$[2, 2]$$$ 放回到集合中。
- Alice 选择了范围 $$$[2, 2]$$$。鲍勃选择了数字$$$2$$$。比赛结束了。

在第四个测试用例中,游戏以 $$$n = 5$$$ 进行。最初,该集合仅包含一个范围 $$$[1, 5]$$$。游戏的回合如下表所示。

游戏回合爱丽丝挑选的范围鲍勃挑选的数字游戏开始前设定的范围$$$ \{ [1, 5] \} $$$1$$$[1, 5]$$$$$$3$$$$$$ \{ [1, 2], [4, 5] \}$$$2$$$[1, 2]$$$$$$1$$$$$$ \{ [2, 2], [4, 5] \} $$$3$$$[4, 5]$$$$$$5$$$$$$ \{ [2, 2], [4, 4] \} $$$4$$$[2, 2]$$$$$$2$$$$$$ \{ [4, 4] \} $$$5$$$[4, 4]$$$$$$4$$$$$$ \{ \} $$$ (空集)