codeforces-scrape

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

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.