CF1860F.Evaluate RBS
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
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⋅x+b⋅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≤t≤1500 ) — the number of testcases.
The first line of each testcase contains a single integer n ( 1≤n≤1500 ).
The i -th of the next 2n lines contains two integers ai and bi ( 1≤ai,bi≤106 ) and a character ci ( $c_i = $ '(' or $c_i = $ ')'). Exactly n tuples have $c_i = $ '(' and the other n tuples have ci= ')'.
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⋅1+0.1⋅4=10.4 and 10⋅2+0.1⋅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 "(()(()))".