1132A.md (1846B)
1 Source: https://codeforces.com/problemset/problem/1132/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 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 A string is called bracket sequence if it does not contain any characters other than "(" and ")". A bracket sequence is called regular if it it is possible to obtain correct arithmetic expression by inserting characters "+" and "1" into this sequence. For example, "", "(())" and "()()" are regular bracket sequences; "))" and ")((" are bracket sequences (but not regular ones), and "(a)" and "(1)+(1)" are not bracket sequences at all. 22 23 You have a number of strings; each string is a bracket sequence of length $2$. So, overall you have $cnt_1$ strings "((", $cnt_2$ strings "()", $cnt_3$ strings ")(" and $cnt_4$ strings "))". You want to write all these strings in some order, one after another; after that, you will get a long bracket sequence of length $2(cnt_1 + cnt_2 + cnt_3 + cnt_4)$. You wonder: is it possible to choose some order of the strings you have such that you will get a regular bracket sequence? Note that you may not remove any characters or strings, and you may not add anything either. 24 25 Input 26 27 The input consists of four lines, $i$-th of them contains one integer $cnt_i$ ($0 \le cnt_i \le 10^9$). 28 29 Output 30 31 Print one integer: $1$ if it is possible to form a regular bracket sequence by choosing the correct order of the given strings, $0$ otherwise. 32 33 Examples 34 35 Input 36 37 ``` 38 3 39 1 40 4 41 3 42 ``` 43 44 Output 45 46 ``` 47 1 48 ``` 49 50 Input 51 52 ``` 53 0 54 0 55 0 56 0 57 ``` 58 59 Output 60 61 ``` 62 1 63 ``` 64 65 Input 66 67 ``` 68 1 69 2 70 3 71 4 72 ``` 73 74 Output 75 76 ``` 77 0 78 ``` 79 80 Note 81 82 In the first example it is possible to construct a string "(())()(()((()()()())))", which is a regular bracket sequence. 83 84 In the second example it is possible to construct a string "", which is a regular bracket sequence.