Codeforces849a odds and ends

Posted by yjjr's blog on February 6, 2018

标签:模拟

Where do odds begin, and where do they end?Where does hope emerge, and will they ever break?

Given an integer sequencea1, a2, ..., an of lengthn. Decide whether it is possible to divide it intoan odd number of non-empty subsegments, the each of which has an odd length andbegins and ends with odd numbers.

A subsegment is a contiguous slice of thewhole sequence. For example, {3, 4, 5} and {1} are subsegments of sequence {1, 2, 3, 4, 5, 6}, while {1, 2, 4} and {7} are not.

Input

The first line of input contains anon-negative integern (1 ≤ n ≤ 100) — the length of the sequence.

The second line containsn space-separatednon-negative integersa1, a2, ..., an (0 ≤ ai ≤ 100) — the elementsof the sequence.

Output

Output "Yes" if it's possible tofulfill the requirements, and "No" otherwise.

You can output each letter in any case(upper or lower).

Example

Input

3
1 3 5

Output

Yes

Input

5
1 0 1 5 1

Output

Yes

Input

3
4 3 1

Output

No

Input

4
3 9 9 3

Output

No

Note

In the first example, divide the sequenceinto 1 subsegment: {1, 3, 5} and therequirements will be met.

In the second example, divide the sequenceinto 3 subsegments: {1, 0, 1}, {5}, {1}.

In the third example, one of thesubsegments must start with 4 which is an even number, thus the requirementscannot be met.

In the fourth example, the sequence can bedivided into 2 subsegments: {3, 9, 9}, {3}, but this is not a valid solution because 2 is an evennumber.

 

题意:给定一个序列,判断其是否可以分成奇数个非空的子段,并且这些子段长度都为奇数,开头和结尾都是奇数

分析:用递归的写法,从头开始找当前最长的子段,暴力枚举,水题

参考代码

#include<bits/stdc++.h>
inline int read() 
{
	int f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,ans=0,flag;
int a[105];

void work(int l,int r)
{
	if(a[l]%2==0){flag=0;return;}
	int i;
	ans++;//printf("%d %d %d\n",l,r,ans);
	for(i=r;i>=l;i--)
	    if((i-l)%2==0&&a[i]%2!=0){break;}
	if(i<r)work(i+1,r);
}
int main()
{
	for(int i=1;i<105;i++)a[i]=2;
    n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    if(a[1]%2==0||a[n]%2==0){printf("No\n");return 0;}
    flag=1;
    work(1,n);
    if(ans%2==0||flag==0)printf("No\n");
    else printf("Yes\n");
    return 0;
}



本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr