← 返回题目列表

Codeforces · 1872/B

B. 走廊或来回

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

你正处于一条向右无限延伸的走廊中,分为方形房间。您从 $$$1$$$ 房间开始,前往 $$$k$$$ 房间,然后返回 $$$1$$$ 房间。您可以选择 $$$k$$$ 的值。搬到相邻的房间需要花费 $$$1$$$ 秒。

此外,走廊里还有$$$n$$$个陷阱:第$$$i$$$个陷阱位于$$$d_i$$$房间,并且会在你进入$$$房间$$$\boldsymbol{d_i}$$$后$$$s_i$$$秒被激活。一旦陷阱被激活,你就无法进入或离开有该陷阱的房间。

可能的走廊以及您通往 $$$k$$$ 房间并返回的路径的示意图。

确定 $$$k$$$ 的最大值,允许您从 $$$1$$$ 房间前往 $$$k$$$ 房间,然后安全返回 $$$1$$$ 房间。

例如,如果$$$n=1$$$且$$$d_1=2,s_1=2$$$,你可以前往$$$k=2$$$房间并安全返回(此时陷阱将激活$$$1+s_1=1+2=3$$$,它不能阻止你返回)。但如果你试图到达$$$k=3$$$房间,陷阱将在$$$1+s_1=1+2=3$$$时刻激活,阻止你返回(你会在第二个$$$3$$$返回时尝试进入房间$$$2$$$,但激活的陷阱会阻止你)。 $$$k$$$ 任何更大的值也是不可行的。因此,答案是$$$k=2$$$。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

测试用例的描述如下。

每个测试用例描述的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 陷阱数量。

每个测试用例描述的以下 $$$n$$$ 行显示两个整数 $$$d_i$$$ 和 $$$s_i$$$ ($$$1 \le d_i, s_i \le 200$$$) - 陷阱的参数(您必须严格在进入该房间后 $$$s_i$$$ 秒过去之前离开房间 $$$d_i$$$ )。多个陷阱可能会占据一个房间($$$d_i$$$ 的值可以重复)。

输出

对于每个测试用例,打印 $$$k$$$ 的最大值,该最大值允许您前往房间 $$$k$$$ 并返回房间 $$$1$$$ 而不会遇到活动陷阱。

示例

输入 #1

7
1
2 2
3
2 8
4 3
5 2
1
200 200
4
1 20
5 9
3 179
100 1
2
10 1
1 18
2
1 1
1 2
3
1 3
1 1
1 3

输出 #1

2
5
299
9
9
1
1

注意

第一个测试用例在上面的问题陈述中进行了解释。

在第二个测试用例中,第二个陷阱阻止您实现 $$$k\ge6$$$。如果$$$k\ge6$$$,第二个陷阱将在$$$3+s_2=3+3=6$$$时刻激活(你进入房间$$$4$$$加上$$$s_2$$$的时间)。如果是$$$k\ge6$$$,您将在$$$7$$$或更晚的时间返回$$$4$$$房间。那时陷阱将被激活。可以证明,可以在不遇到活动陷阱的情况下到达房间 $$$k=5$$$。

在第三个测试用例中,您可以到达房间$$$299$$$,然后立即返回房间$$$1$$$。