Regular Bracket Sequence(思维)

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.
You have a number of strings; each string is a bracket sequence of length 2
. So, overall you have 𝑐𝑛𝑡1 strings "((", 𝑐𝑛𝑡2 strings "()", 𝑐𝑛𝑡3 strings ")(" and 𝑐𝑛𝑡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(𝑐𝑛𝑡1+𝑐𝑛𝑡2+𝑐𝑛𝑡3+𝑐𝑛𝑡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.

Input

The input consists of four lines, 𝑖-th of them contains one integer 𝑐𝑛𝑡𝑖 (0≤𝑐𝑛𝑡𝑖≤109).

Output

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.

Examples

Input

Copy

3
1
4
3

Output

Copy

1

Input

Copy

0
0
0
0

Output

Copy

1

Input

Copy

1
2
3
4

Output

Copy

0

Note

In the first example it is possible to construct a string "(())()(()((()()()())))", which is a regular bracket sequence.

In the second example it is possible to construct a string "", which is a regular bracket sequence.

当:

  1. a==d时一定成立,输出1否则输出为0。
  2. 剩下的情况只有 a==d==0且c==0才为1,否则为0。
  3. 补充:ad配对,b自己就合理,c使用时必须放在ad内部

被hack的代码:

#include <iostream>
using namespace std;
typedef long long LL;
int main()
{
  LL a, b, c, d;
  cin >> a >> b >> c >> d;
  bool flag = 1;
  if (a != d) flag = 0;
  if (a == 0 && b == 0 && d == 0) flag = (c == 0) ? 1 : 0;
  if (flag)
    cout << "1" << endl;
  else cout << "0" << endl;
  return 0;
}

AC代码

#include <iostream>
using namespace std;
typedef long long LL;
int main()
{
  LL a, b, c, d;
  cin >> a >> b >> c >> d;
  bool flag = 1;
  if (a == d)
  {
    if (a == 0 && c == 0 || a != 0)
      cout << "1" << endl;
    else cout << "0" << endl;
  }
  else cout << "0" << endl;
  return 0;
}

 

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注

19 + 5 =