codeforces-scrape

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

612C.md (1384B)


      1 Source: https://codeforces.com/problemset/problem/612/C
      2 
      3 C. Replace To Make Regular Bracket Sequence
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 You are given string *s* consists of opening and closing brackets of four kinds <>, {}, [], (). There are two types of brackets: opening and closing. You can replace any bracket by another of the same type. For example, you can replace < by the bracket {, but you can't replace it by ) or >.
     22 
     23 The following definition of a regular bracket sequence is well-known, so you can be familiar with it.
     24 
     25 Let's define a regular bracket sequence (RBS). Empty string is RBS. Let *s*1 and *s*2 be a RBS then the strings <*s*1>*s*2, {*s*1}*s*2, [*s*1]*s*2, (*s*1)*s*2 are also RBS.
     26 
     27 For example the string "[[(){}]<>]" is RBS, but the strings "[)()" and "][()()" are not.
     28 
     29 Determine the least number of replaces to make the string *s* RBS.
     30 
     31 Input
     32 
     33 The only line contains a non empty string *s*, consisting of only opening and closing brackets of four kinds. The length of *s* does not exceed 106.
     34 
     35 Output
     36 
     37 If it's impossible to get RBS from *s* print Impossible.
     38 
     39 Otherwise print the least number of replaces needed to get RBS from *s*.
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 [<}){}
     47 ```
     48 
     49 Output
     50 
     51 ```
     52 2
     53 ```
     54 
     55 Input
     56 
     57 ```
     58 {()}[]
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 0
     65 ```
     66 
     67 Input
     68 
     69 ```
     70 ]]
     71 ```
     72 
     73 Output
     74 
     75 ```
     76 Impossible
     77 ```