codeforces-scrape

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

26B.md (968B)


      1 Source: https://codeforces.com/problemset/problem/26/B
      2 
      3 B. Regular Bracket Sequence
      4 
      5 time limit per test
      6 
      7 5 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     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.
     22 
     23 One day Johnny got bracket sequence. He decided to remove some of the brackets from it in order to obtain a regular bracket sequence. What is the maximum length of a regular bracket sequence which can be obtained?
     24 
     25 Input
     26 
     27 Input consists of a single line with non-empty string of «(» and «)» characters. Its length does not exceed 106.
     28 
     29 Output
     30 
     31 Output the maximum possible length of a regular bracket sequence.
     32 
     33 Examples
     34 
     35 Input
     36 
     37 ```
     38 (()))(
     39 ```
     40 
     41 Output
     42 
     43 ```
     44 4
     45 ```
     46 
     47 Input
     48 
     49 ```
     50 ((()())
     51 ```
     52 
     53 Output
     54 
     55 ```
     56 6
     57 ```