Informatica Online Judge

  홀수나라의 순열 분할 [1959 / 07A7]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 35   Total Tried : 46


The Champion of this Problem (C++) : gs16109 - 0ms / 100byte
My Best Submission (C++) : N/A

[Codeforces]

Background

홀수 나라에서는 무조건 홀수를 좋아한다.

순열 $A$가 주어진다.

순열 $A$는 $a_1, a_2, ... a_n$으로 이루어진 $n$개의 수로 구성된다.

이 나라에 사는 경곽이는 이 순열을 1개 이상의 부분열(subsegment)로 나누려고 한다.

부분열은 길이가 $1$이상 $n$이하인 연속된 원소들의 집합을 말한다.

예를들어 {1, 2, 3, 4, 5, 6}이 원래 순열이라면

{1}, {2, 3, 4}, {5, 6} 의 3개의 부분열로 나눌 수도 있으며

{1, 2, 3}, {4, 5, 6} 의 2개의 부분열로도 나눌 수 있다.

이 문제에서는 부분열로 나눌 때 다음과 같은 규칙을 지켜야 한다.

- 부분열의 개수는 반드시 홀수개이어야 한다.
- 나눠진 각 부분열의 원소의 개수도 반드시 홀수개이어야 한다.
- 나눠진 각 부분열의 시작 원소와 끝 원소는 반드시 홀수이어야 한다.

위 규칙을 모두 만족하도록 분해하는 것이 가능한지 판단하는 프로그램을 작성하시오.

Input

$n$

${a_1}~~{a_2}~~...~~{a_n}~~$

[입력값의 정의역]
$1≤n≤100$
$1≤a_i≤100$

Output

조건에 맞도록 분해할 수 있다면 "Yes"를 출력하고, 그렇지 않다면 "No"를 출력한다. (따옴표는 제외)

IO Example

입력
3
1 3 5

출력
Yes

* 설명 : 전체를 하나의 부분열로 보면 부분열의 수 1개, 부분열 내의 원소의 수 3개, 부분열의 시작원소 1, 끝원소 5이므로 모두 홀수를 만족하므로 가능!!

입력2
3
4 3 1

출력2
No

* 설명 : 이 경우는 어떻게 나누더라도 위 조건을 만족할 수 없으므로 불가능.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]