codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1469A.md (1743B)


      1 Source: https://codeforces.com/problemset/problem/1469/A
      2 
      3 A. Regular Bracket Sequence
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 512 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 A bracket sequence is called regular if it is possible to obtain correct arithmetic expression by inserting characters + and 1 into this sequence. For example, sequences (())(), () and (()(())) are regular, while )(, (() and (()))( are not. Let's call a regular bracket sequence "RBS".
     22 
     23 You are given a sequence $s$ of $n$ characters (, ), and/or ?. There is exactly one character ( and exactly one character ) in this sequence.
     24 
     25 You have to replace every character ? with either ) or ( (different characters ? can be replaced with different brackets). You cannot reorder the characters, remove them, insert other characters, and each ? must be replaced.
     26 
     27 Determine if it is possible to obtain an RBS after these replacements.
     28 
     29 Input
     30 
     31 The first line contains one integer $t$ ($1 \le t \le 1000$) — the number of test cases.
     32 
     33 Each test case consists of one line containing $s$ ($2 \le |s| \le 100$) — a sequence of characters (, ), and/or ?. There is exactly one character ( and exactly one character ) in this sequence.
     34 
     35 Output
     36 
     37 For each test case, print YES if it is possible to obtain a regular bracket sequence, or NO otherwise}.
     38 
     39 You may print each letter in any case (for example, YES, Yes, yes, yEs will all be recognized as positive answer).
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 5
     47 ()
     48 (?)
     49 (??)
     50 ??()
     51 )?(?
     52 ```
     53 
     54 Output
     55 
     56 ```
     57 YES
     58 NO
     59 YES
     60 YES
     61 NO
     62 ```
     63 
     64 Note
     65 
     66 In the first test case, the sequence is already an RBS.
     67 
     68 In the third test case, you can obtain an RBS as follows: ()() or (()).
     69 
     70 In the fourth test case, you can obtain an RBS as follows: ()().