Codeforces Round #431 (Div. 2)

A. Odds and Ends

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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

Given an integer sequence?a1,?a2,?...,?an?of length?n. Decide whether it is possible to divide it into an odd number of non-empty subsegments, the each of which has an odd length and begins and ends with odd numbers.

A?subsegment?is a contiguous slice of the whole 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 a non-negative integer?n?(1?≤?n?≤?100) — the length of the sequence.

The second line contains?n?space-separated non-negative integers?a1,?a2,?...,?an?(0?≤?ai?≤?100) — the elements of the sequence.

Output

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

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

Examples

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 sequence into?1?subsegment:?{1,?3,?5}?and the requirements will be met.

In the second example, divide the sequence into?3?subsegments:?{1,?0,?1},?{5},?{1}.

In the third example, one of the subsegments must start with?4?which is an even number, thus the requirements cannot be met.

In the fourth example, the sequence can be divided into?2?subsegments:?{3,?9,?9},?{3}, but this is not a valid solution because?2?is an even number.

問你把長度為n的序列化為奇數開頭奇數結尾而且個數是奇數的數列

首先分析偶數，湊兩個奇數數列，然后這個子序列個數就又是偶數了

所以只有奇數個符合要求，開頭結尾必須是，合并為一個就好了

我錯了是因為優先級 判斷末位是不是奇數要用 (n&1)==0

#include<bits/stdc++.h>
using namespace std;
int main()
{int n;cin>>n;int a[102];for(int i=1;i<=n;i++)cin>>a[i];int f=0;if(n&1&&a[1]&1&&a[n]&1)f=1;printf("%s",f?"Yes":"No");return 0;
}

B. Tell Your World

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Connect the countless points with lines, till we reach the faraway yonder.

There are?n?points on a coordinate plane, the?i-th of which being?(i,?yi).

Determine whether it's possible to draw two parallel and non-overlapping lines, such that every point in the set lies on?exactly one?of them, and each of them passes through?at least one?point in the set.

Input

The first line of input contains a positive integer?n?(3?≤?n?≤?1?000) — the number of points.

The second line contains?n?space-separated integers?y1,?y2,?...,?yn?(?-?109?≤?yi?≤?109) — the vertical coordinates of each point.

Output

Output "Yes" (without quotes) if it's possible to fulfill the requirements, and "No" otherwise.

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

Examples

input

5
7 5 8 6 9

output

Yes

input

5
-1 -2 0 0 -5

output

No

input

5
5 4 3 2 1

output

No

input

5
1000000000 0 0 0 0

output

Yes

Note

In the first example, there are five points:?(1,?7),?(2,?5),?(3,?8),?(4,?6)?and?(5,?9). It's possible to draw a line that passes through points?1,?3,?5, and another one that passes through points?2,?4?and is parallel to the first one.

In the second example, while it's possible to draw two lines that cover all points, they cannot be made parallel.

In the third example, it's impossible to satisfy both requirements at the same time.

?

?這個題嘛就是給你一堆點，讓你判斷在不在兩條平行（不重合）的直線上

我選用前三個點在不在一條直線上，在的話就是其他點還有一條直線

不在的話就分三種情況討論

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a[1005];int n;
bool check()
{int f=-1;LL f1=a[3]-a[2];if(a[2]*2==a[1]+a[3]){for(int i=4; i<=n; i++){if((a[i]-a[1])!=(i-1)*f1){if(f==-1)f=i;else{if((a[i]-a[f])!=(i-f)*f1){return 0;}}}}if(f==-1){return 0;}}else{f=0,f1=a[2]-a[1];for(int i=4; i<=n; i++){if((a[i]-a[1])!=(i-1)*f1&&((a[i]-a[3])!=(i-3)*f1)){f++;break;}}f1=a[3]-a[2];for(int i=4; i<=n; i++){if((a[i]-a[2])!=(i-2)*f1&&((a[i]-a[1])!=(i-1)*f1)){f++;break;}}f1=a[3]-a[1];for(int i=4; i<=n; i++){if(2*(a[i]-a[2])!=(i-2)*f1&&(2*(a[i]-a[1])!=(i-1)*f1)){f++;break;}}if(f==3)return 0;}return 1;
}
int main()
{scanf("%d",&n);for(int i=1; i<=n; i++)scanf("%lld",a+i);if(!check())printf("No\n");else printf("Yes\n");return 0;
}

這個寫法好啊

?

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1005;
ll y[N];
int n;
bool gx(int a,int b,int c,int d)
{return (b-a)*(y[d]-y[c])==(d-c)*(y[b]-y[a]);
}
int check(int d,int f)
{vector<int>V;for(int i=1; i<=n; i++)if(!gx(d,f,f,i))V.push_back(i);if(V.size()==0)return 0;if(V.size()==1)return 1;for(int i=1; i<(int)V.size(); i++)if(!gx(d,f,V[i],V[i-1]))return 0;return 1;
}
int main()
{cin>>n;for(int i=1; i<=n; i++)cin>>y[i];if(check(1,2)||check(2,3)||check(1,3))cout<<"YES";else cout<<"NO";return 0;
}

?

C. From Y to Y

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

From beginning till end, this message has been waiting to be conveyed.

For a given unordered multiset of?n?lowercase English letters ("multi" means that a letter may appear more than once), we treat all letters as strings of length?1, and repeat the following operation?n?-?1?times:

• Remove any two elements?s?and?t?from the set, and add their concatenation?s?+?t?to the set.

The cost of such operation is defined to be?, where?f(s,?c)?denotes the number of times character?c?appears in string?s.

Given a non-negative integer?k, construct any valid non-empty set of no more than?100?000?letters, such that the minimum accumulative cost of the whole process is?exactly?k. It can be shown that a solution always exists.

Input

The first and only line of input contains a non-negative integer?k?(0?≤?k?≤?100?000) — the required minimum cost.

Output

Output a non-empty string of no more than?100?000?lowercase English letters — any multiset satisfying the requirements, concatenated to be a string.

Note that the printed string doesn't need to be the final concatenated string. It only needs to represent an unordered multiset of letters.

Examples

input

12

output

abababab

input

3

output

codeforces

Note

For the multiset {'a',?'b',?'a',?'b',?'a',?'b',?'a',?'b'}, one of the ways to complete the process is as follows:

• {"ab",?"a",?"b",?"a",?"b",?"a",?"b"}, with a cost of?0;
• {"aba",?"b",?"a",?"b",?"a",?"b"}, with a cost of?1;
• {"abab",?"a",?"b",?"a",?"b"}, with a cost of?1;
• {"abab",?"ab",?"a",?"b"}, with a cost of?0;
• {"abab",?"aba",?"b"}, with a cost of?1;
• {"abab",?"abab"}, with a cost of?1;
• {"abababab"}, with a cost of?8.

The total cost is?12, and it can be proved to be the minimum cost of the process.

?

?就是貪心構造，合并花費是0，但是連續的某個字母生成的話費是n*（n-1）/2，每次生成最多就好的

#include <bits/stdc++.h>
using namespace std;
int a[500];
int main()
{int k;scanf("%d",&k);for(int i=1;i<450;i++)a[i]=i*(i-1)/2;if(k==0)printf("a");else{int f=0;char c='a';while(k){int pos=lower_bound(a+1,a+450,k)-a;if(a[pos]>k)pos--;for(int i=0;i<pos;i++)printf("%c",c);k-=a[pos];c++;}}return 0;
}

?