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 ```