← 返回题目列表

Codeforces · 1860/F

F. 评估 RBS

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

给定 $$$2n$$$ 值 $$$(a, b, c)$$$ 的元组,其中 $$$a$$$ 和 $$$b$$$ 是正整数,$$$c$$$ 是括号“(”或“)”。确切地说,$$$n$$$ 元组具有 $$$c = $$$'(',其他 $$$n$$$ 元组具有 $$$c =$$$ ')'。

要求您选择两个正值 $$$x$$$ 和 $$$y$$$($$$x > 0$$$ 和 $$$y > 0$$$;不一定是整数),并按 $$$a \cdot x + b \cdot y$$$ 的递增值对元组进行排序。如果多个元组具有相同的值,则可以将它们按任意顺序放置。

是否可以选择这样的 $$$x$$$ 和 $$$y$$$ ,以按结果顺序从元组中取出括号 $$$c$$$ 产生规则的括号序列?

正则括号序列是通过在序列的原始字符之间插入字符“1”和“+”可以将括号序列转换为正确的算术表达式。

输入

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

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

接下来的 $$$2n$$$ 行的第 $$$i$$$ 行包含两个整数 $$$a_i$$$ 和 $$$b_i$$$ ($$$1 \le a_i, b_i \le 10^6$$$) 和一个字符 $$$c_i$$$ ($$$c_i = $$$'(' 或 $$$c_i = $$$')')。确切地说,$$$n$$$ 元组具有 $$$c_i = $$$'(',其他 $$$n$$$ 元组具有 $$$c_i =$$$ ')'。

所有测试用例的 $$$n$$$ 总和不超过 $$$1500$$$。

输出

对于每个测试用例,如果可以选择这样的 $$$x$$$ 和 $$$y$$$ ,从元组中按结果顺序取出括号 $$$c$$$ 会产生规则的括号序列,则打印“YES”。否则,打印“NO”。

示例

输入 #1

4
1
1 4 (
2 3 )
1
1 2 )
3 4 (
4
16 5 (
12 3 (
19 6 )
4 10 )
3 10 )
19 11 (
19 7 )
7 14 (
4
16 8 (
11 9 )
20 10 )
20 19 )
2 13 (
18 7 (
15 19 )
5 6 (

输出 #1

YES
NO
NO
YES

注意

在第一个测试用例中,您可以选择 $$$x = 10, y = 0.1$$$。元组的值将为 $$$10 \cdot 1 + 0.1 \cdot 4 = 10.4$$$ 和 $$$10 \cdot 2 + 0.1 \cdot 3 = 20.3$$$。因此,第一个元组将首先出现,然后是第二个元组,从而形成括号序列“()”,这是常规的。

在第二个测试用例中,您不能选择正 $$$x$$$ 和 $$$y$$$ ,这样左括号被分配的值小于或等于右括号的值。

在第四个测试用例中,您可以选择$$$x = 0.6,y = 0.55$$$。括号序列为“(()(()))”。