홀수로 나눠라! 짝수로 나눠라!

면접 대비

시간 제한1초메모리 제한1024 MB

요약

양의 정수 수열을 연속된 구간으로 나눌 때, 모든 구간의 합이 홀수이고 구간 개수도 홀수이거나, 합이 모두 짝수이고 개수가 짝수인 분할이 가능한지 판별합니다.

난이도: 쉬움10점 중 3점
유형: 수학, 배열
정답자: 아직 제출이 없습니다

문제

양의 정수로 이루어진 길이 $N$ 의 수열 $A$ 가 주어진다. 연속된 원소들을 묶어 수열을 한 개 이상의 집합으로 나눠야 한다. 집합을 나눌 때는 홀수로 나누기 또는 짝수로 나누기 중 한 가지 방법을 선택할 수 있다. 수열의 모든 원소는 나눈 집합 중 정확히 하나에 속해야 한다.

홀수로 나누기
- 각 집합의 원소 합은 홀수여야 한다.
- 수열을 홀수 개의 집합으로 나눠야 한다.
짝수로 나누기
- 각 집합의 원소 합은 짝수여야 한다.
- 수열을 짝수 개의 집합으로 나눠야 한다.

선택한 방법으로 주어진 수열을 한 개 이상의 집합으로 나눌 수 있는지 판별하자.

입력

첫째 줄에 수열 $A$ 의 길이 $N$ 이 주어진다. $1\leq N\leq 200,000$

둘째 줄에 수열의 원소 $A_i$ 가 공백으로 구분되어 주어진다. $1\leq A_i\leq 10^9$

출력

주어진 방법 중 하나를 선택해 수열을 한 개 이상의 집합으로 나눌 수 있으면 1을, 없으면 0을 출력한다.

힌트

입출력의 양이 많으므로 빠른 입출력을 사용하는 것을 권장한다. 언어별 빠른 입출력 방법은 아래와 같다.

C++: cin, cout을 사용하는 경우 입출력 전에 cin.tie(nullptr); ios::sync_with_stdio(false);를 한 번 적용해야 한다. 줄 바꿈할 때는 endl 대신 '\n'을 사용해야 한다.
Java: BufferedReader와 BufferedWriter를 사용해야 한다.
Python3, PyPy3: input() 대신 sys.stdin.readline().rstrip()을 사용해야 한다.

예제3

예제 1
입력
```
5
1 2 1 2 1
```
예상 출력
```
1
```
예제 2
입력
```
6
1 2 4 4 2 1
```
예상 출력
```
0
```
예제 3
입력
```
7
1 2 4 3 2 2 2
```
예상 출력
```
1
```