A16104. Evaluate RBS
编程题
普及/提高-
知识点
题目描述
You are given $2n$ tuples of values $(a, b, c)$ , where $a$ and $b$ are positive integers and $c$ is a bracket '(' or ')'. Exactly $n$ tuples have $c = $ '(' and the other $n$ tuples have $c =$ ')'.
You are asked to choose two positive values $x$ and $y$ ( $x > 0$ and $y > 0$ ; not necessarily integers) and sort the tuples in the increasing value of $a \cdot x + b \cdot y$ . If several tuples have the same value, you can place them in any order among themselves.
Is it possible to choose such $x$ and $y$ that taking brackets $c$ from the tuples in the resulting order produces a regular bracket sequence?
A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters "1" and "+" between the original characters of the sequence.
You are asked to choose two positive values $x$ and $y$ ( $x > 0$ and $y > 0$ ; not necessarily integers) and sort the tuples in the increasing value of $a \cdot x + b \cdot y$ . If several tuples have the same value, you can place them in any order among themselves.
Is it possible to choose such $x$ and $y$ that taking brackets $c$ from the tuples in the resulting order produces a regular bracket sequence?
A regular bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters "1" and "+" between the original characters of the sequence.
输入格式
The first line contains a single integer $t$ ( $1 \le t \le 1500$ ) — the number of testcases.
The first line of each testcase contains a single integer $n$ ( $1 \le n \le 1500$ ).
The $i$ -th of the next $2n$ lines contains two integers $a_i$ and $b_i$ ( $1 \le a_i, b_i \le 10^6$ ) and a character $c_i$ ( $c_i = $ '(' or $c_i = $ ')'). Exactly $n$ tuples have $c_i = $ '(' and the other $n$ tuples have $c_i =$ ')'.
The sum of $n$ over all testcases doesn't exceed $1500$ .
The first line of each testcase contains a single integer $n$ ( $1 \le n \le 1500$ ).
The $i$ -th of the next $2n$ lines contains two integers $a_i$ and $b_i$ ( $1 \le a_i, b_i \le 10^6$ ) and a character $c_i$ ( $c_i = $ '(' or $c_i = $ ')'). Exactly $n$ tuples have $c_i = $ '(' and the other $n$ tuples have $c_i =$ ')'.
The sum of $n$ over all testcases doesn't exceed $1500$ .
输出格式
For each testcase, print "YES" if it's possible to choose such $x$ and $y$ that taking brackets $c$ from the tuples in the resulting order produces a regular bracket sequence. Otherwise, print "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
说明/提示
In the first testcase, you can choose $x = 10, y = 0.1$ . The values for tuples will be $10 \cdot 1 + 0.1 \cdot 4 = 10.4$ and $10 \cdot 2 + 0.1 \cdot 3 = 20.3$ . Thus, the first tuple will go first, then the second one, making the bracket sequence "()", which is regular.
In the second testcase, you can't choose positive $x$ and $y$ such that the opening brackets gets assigned a value less or equal to the value of the closing bracket.
In the fourth testcase, you can choose $x = 0.6, y = 0.55$ . The bracket sequence is "(()(()))".
In the second testcase, you can't choose positive $x$ and $y$ such that the opening brackets gets assigned a value less or equal to the value of the closing bracket.
In the fourth testcase, you can choose $x = 0.6, y = 0.55$ . The bracket sequence is "(()(()))".