Codeforces Global Round 2

A.Ilya and a Colorful Walk

time limit per test2 seconds memory limit per test256 megabytes

Ilya lives in a beautiful city of Chordalsk.

There are ?n houses on the street Ilya lives, they are numerated from 11 to ?n from left to right; the distance between every two neighboring houses is equal to 11 unit. The neighboring houses are 11 and 22, 22 and 33, ..., ?−1n−1 and ?n. The houses ?n and 11 are not neighboring.

The houses are colored in colors ?1,?2,…,??c1,c2,…,cn so that the ?i-th house is colored in the color ??ci. Everyone knows that Chordalsk is not boring, so there are at least two houses colored in different colors.

Ilya wants to select two houses ?i and ?j so that 1≤?<?≤?1≤i<j≤n, and they have different colors: ??≠??ci≠cj. He will then walk from the house ?ito the house ?j the distance of (?−?)(j−i) units.

Ilya loves long walks, so he wants to choose the houses so that the distance between them is the maximum possible.

Help Ilya, find this maximum possible distance.Input

The first line contains a single integer ?n (3≤?≤3000003≤n≤300000) — the number of cities on the street.

The second line contains ?n integers ?1,?2,…,??c1,c2,…,cn (1≤??≤?1≤ci≤n) — the colors of the houses.

It is guaranteed that there is at least one pair of indices ?i and ?j so that 1≤?<?≤?1≤i<j≤n and ??≠??ci≠cj.Output

Print a single integer — the maximum possible distance Ilya can walk.
Examples
input

5 
1 2 3 2 3

output

4

input

3 
1 2 1

output

1

input

7 
1 1 3 1 1 1 1

output

4

Note

In the first example the optimal way is to walk from the first house to the last one, where Ilya can walk the distance of 5−1=45−1=4 units.

In the second example the optimal way is to either walk from the first house to the second or from the second to the third. Both these ways have the distance of 11 unit.

In the third example the optimal way is to walk from the third house to the last one, where Ilya can walk the distance of 7−3=47−3=4 units.

贪心,答案肯定包含第一座房子或者最后一座房子,证明如下:

如果存在某个方案是选择 ai​ 和 aj​ (1<i<j<n,ci!=cj)(1<i<j<n,ci​!=cj​) 的

那么

如果 a1​ 和 ai​ 颜色一样,那 a1​ 和 aj​ 这个方案更优。

如果 a1​ 和 ai​ 颜色不一样,并且 a1​ 和 aj​ 颜色也不一样,那 a1​ 和 aj​ 这个方案更优。

如果 aj​ 和 an​ 颜色一样,那 ai​ 和 an​ 这个方案更优。

如果 aj​ 和 an​ 颜色不一样,并且 ai​ 和 an​ 颜色也不一样,那 ai​ 和 an​ 这个方案更优。

如果 a1​ 和 aj​ 颜色一样 并且 ai​ 和 an​ 颜色一样呢?

那么因为 ai​ 与 aj​ 颜色不一样所以 a1​ 与 an​ 颜色也不一样啊!那没有比 “a1​ 和 an​” 这个方案更好的方案了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=(int)3e5+100;
const int mod=(int)1e9+7;
int main(){
	ios::sync_with_stdio(0);
	int n;cin>>n;
	int a[maxn];
	int ans=0;
	for(int i=1;i<=n;++i){
		cin>>a[i];
		if(a[i]!=a[1]) ans=i-1;
	}
	for(int i=1;i<=n;++i){
		if(a[i]!=a[n]) {
			ans=max(ans,n-i);
			break;
		}
	}
	cout<<ans<<endl;
}


B. Alyona and a Narrow Fridge

time limit per test1 second memory limit per test256 megabytes

Alyona has recently bought a miniature fridge that can be represented as a matrix with ℎh rows and 22 columns. Initially there is only one shelf at the bottom of the fridge, but Alyona can install arbitrary number of shelves inside the fridge between any two rows. A shelf is two cells wide, does not occupy any space but separates the inside of the fridge to the lower and upper part.

An example of a fridge with ℎ=7h=7 and two shelves. The shelves are shown in black. The picture corresponds to the first example.

Alyona has ?n bottles of milk that she wants to put in the fridge. The ?i-th bottle is ??ai cells tall and 11 cell wide. She can put a bottle on some shelf if the corresponding space above the shelf is at least as tall as the bottle. She can not put a bottle on top of another bottle (if there is no shelf between them). Two bottles can not share a cell.

Alyona is interested in the largest integer ?k such that she can put bottles 11, 22, ..., ?k in the fridge at the same time. Find this largest ?k.Input

The first line contains two integers ?n and ℎh (1≤?≤1031≤n≤103, 1≤ℎ≤1091≤h≤109) — the number of bottles and the height of the fridge.

The second line contains ?n integers ?1a1, ?2a2, ..., ??an (1≤??≤ℎ1≤ai≤h) — the heights of the bottles.Output

Print the single integer ?k — the maximum integer such that Alyona can put the bottles 11, 22, ..., ?k in the fridge at the same time. If Alyona can put all bottles in the fridge, print ?n. It is easy to see that Alyona can always put at least one bottle in the fridge.
Examples
input

5 7 
2 3 5 4 1

output

3

input

10 10 
9 1 1 1 1 1 1 1 1 1

output

4

input

5 10 
3 1 4 2 4

output

5

Note

One of optimal locations in the first example is shown on the picture in the statement.

One of optimal locations in the second example is shown on the picture below.

One of optimal locations in the third example is shown on the picture below.

贪心,对所有瓶子进行排序,那么每次选相邻高度的瓶子一定是最优的(反证法),所以每次累加的高度都是两个瓶子中较高的那个,直到sum>h就放不下了

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int maxn=(int)1e3+100;
const int mod=(int)1e9+7;
int main(){
	ios::sync_with_stdio(0);
	int n,h;cin>>n>>h;
	vector<int> a(n);
	for(int i=0;i<n;++i) cin>>a[i];
	for(int ans=n;ans>0;--ans){
		vector<int> b(a.begin(),a.begin()+ans);
		sort(b.begin(),b.end(),greater<int>());
		ll sum=0;
		for(int i=0;i<ans;i+=2){
			sum+=b[i];
		}
		if(sum<=h) {
			cout<<ans<<endl;
			exit(0);
		}
	}
	exit(0);
}


C. Ramesses and Corner Inversion

time limit per test1 second memory limit per test256 megabytes

Ramesses came to university to algorithms practice, and his professor, who is a fairly known programmer, gave him the following task.

You are given two matrices ?A and ?B of size ?×?n×m, each of which consists of 00 and 11 only. You can apply the following operation to the matrix ?A arbitrary number of times: take any submatrix of the matrix ?A that has at least two rows and two columns, and invert the values in its corners (i.e. all corners of the submatrix that contain 00, will be replaced by 11, and all corners of the submatrix that contain 11, will be replaced by 00). You have to answer whether you can obtain the matrix ?B from the matrix ?A.

An example of the operation. The chosen submatrix is shown in blue and yellow, its corners are shown in yellow.

Ramesses don't want to perform these operations by himself, so he asks you to answer this question.

submatrix of matrix ?M is a matrix which consist of all elements which come from one of the rows with indices ?1,?1+1,…,?2x1,x1+1,…,x2 of matrix ?M and one of the columns with indices ?1,?1+1,…,?2y1,y1+1,…,y2 of matrix ?M, where ?1,?2,?1,?2x1,x2,y1,y2 are the edge rows and columns of the submatrix. In other words, a submatrix is a set of elements of source matrix which form a solid rectangle (i.e. without holes) with sides parallel to the sides of the original matrix. The corners of the submatrix are cells (?1,?1)(x1,y1), (?1,?2)(x1,y2), (?2,?1)(x2,y1), (?2,?2)(x2,y2), where the cell (?,?)(i,j)denotes the cell on the intersection of the ?i-th row and the ?j-th column.Input

The first line contains two integers ?n and ?m (1≤?,?≤5001≤n,m≤500) — the number of rows and the number of columns in matrices ?A and ?B.

Each of the next ?n lines contain ?m integers: the ?j-th integer in the ?i-th line is the ?j-th element of the ?i-th row of the matrix ?A (0≤???≤10≤Aij≤1).

Each of the next ?n lines contain ?m integers: the ?j-th integer in the ?i-th line is the ?j-th element of the ?i-th row of the matrix ?B (0≤???≤10≤Bij≤1).Output

Print "Yes" (without quotes) if it is possible to transform the matrix ?A to the matrix ?B using the operations described above, and "No" (without quotes), if it is not possible. You can print each letter in any case (upper or lower).
Examples
input

3 3 
0 1 0
0 1 0
1 0 0
1 0 0
1 0 0
1 0 0

output

Yes

input

6 7 
0 0 1 1 0 0 1
0 1 0 0 1 0 1
0 0 0 1 0 0 1
1 0 1 0 1 0 0
0 1 0 0 1 0 1
0 1 0 1 0 0 1
1 1 0 1 0 1 1
0 1 1 0 1 0 0
1 1 0 1 0 0 1
1 0 1 0 0 1 0
0 1 1 0 1 0 0
0 1 1 1 1 0 1

output

Yes

input

3 4 
0 1 0 1
1 0 1 0
0 1 0 1
1 1 1 1
1 1 1 1
1 1 1 1

output

No

Note

The examples are explained below.

Example 1.

Example 2.

Example 3.

对于修改前和修改后的两幅图,我们可以证明,如果答案是Yes的话,那么两幅图中每一行每一列不一样的点的个数都是偶数个(奇数个必然不可行)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int maxn=(int)1e3+100;
const int mod=(int)1e9+7;
int ro[550],cr[550];
int main(){
	ios::sync_with_stdio(0);
	int n,m;cin>>n>>m;
	int a[550][550];
	for(int i=0;i<n;++i)
		for(int j=0;j<m;++j){
			cin>>a[i][j];
		}
	for(int i=0;i<n;++i)
		for(int j=0;j<m;++j){
			int x;cin>>x;
			if(a[i][j]!=x){
				ro[i]++; cr[j]++;
			}
		}
	int flag=1;	
	for(int i=0;i<max(n,m);++i){
		if(ro[i]%2||cr[i]%2){
			flag=0;
			break;
		}
	}	
	if(flag) cout<<"Yes\n";
	else cout<<"No\n";
	exit(0);
}


D. Frets On Fire

time limit per test1.5 seconds memory limit per test256 megabytes

Miyako came to the flea kingdom with a ukulele. She became good friends with local flea residents and played beautiful music for them every day.

In return, the fleas made a bigger ukulele for her: it has ?n strings, and each string has (1018+1)(1018+1) frets numerated from 00 to 10181018. The fleas use the array ?1,?2,…,??s1,s2,…,sn to describe the ukulele's tuning, that is, the pitch of the ?j-th fret on the ?i-th string is the integer ??+?si+j.

Miyako is about to leave the kingdom, but the fleas hope that Miyako will answer some last questions for them.

Each question is in the form of: "How many different pitches are there, if we consider frets between ?l and ?r (inclusive) on all strings?"

Miyako is about to visit the cricket kingdom and has no time to answer all the questions. Please help her with this task!

Formally, you are given a matrix with ?n rows and (1018+1)(1018+1) columns, where the cell in the ?i-th row and ?j-th column (0≤?≤10180≤j≤1018) contains the integer ??+?si+j. You are to answer ?q queries, in the ?k-th query you have to answer the number of distinct integers in the matrix from the ??lk-th to the ??rk-th columns, inclusive.Input

The first line contains an integer ?n (1≤?≤1000001≤n≤100000) — the number of strings.

The second line contains ?n integers ?1,?2,…,??s1,s2,…,sn (0≤??≤10180≤si≤1018) — the tuning of the ukulele.

The third line contains an integer ?q (1≤?≤1000001≤q≤100000) — the number of questions.

The ?k-th among the following ?q lines contains two integers ??lk,??rk (0≤??≤??≤10180≤lk≤rk≤1018) — a question from the fleas.Output

Output one number for each question, separated by spaces — the number of different pitches.
Examples
input

6
3 1 4 1 5 9
3
7 7
0 2
8 17

output

5 10 18

input

2
1 500000000000000000
2
1000000000000000000 1000000000000000000
0 1000000000000000000

output

2 1500000000000000000

Note

For the first example, the pitches on the 66 strings are as follows.

There are 55 different pitches on fret 77 — 8,10,11,12,168,10,11,12,16.

There are 1010 different pitches on frets 0,1,20,1,2 — 1,2,3,4,5,6,7,9,10,111,2,3,4,5,6,7,9,10,11.

很显然起始数字的顺序对答案并没有影响,并且我们可以很容易得出[l,r]区间中最大和最小的数,那么现在的问题是有可能有一些区间是不连续的比如说两个数1和4,取[0,1]区间,那么3这个数就取不到,所以很显然取不到的数的个数和区间间断的长度是有关的,并且为线性关系,可以用二分来查找区间差值大于r-l+1的点

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mst(a,b) memset(a,b,sizeof(a))
#define pb push_back
const int maxn=(int)1e5+100;
const int mod=(int)1e9+7;
ll a[maxn],c[maxn],sum[maxn];//原数组,区间差值,差值前缀和
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int n;cin>>n;
	for(int i=0;i<n;++i) cin>>a[i]; sort(a,a+n);
	for(int i=1;i<n;++i) c[i-1]=a[i]-a[i-1]; sort(c,c+n-1);
	sum[0]=c[0];
	for(int i=1;i<n-1;++i) sum[i]=sum[i-1]+c[i];
	int q;cin>>q; int fr=1;
	while(q--){
		ll l,r;cin>>l>>r;
		ll sub=r-l+1; ll ans=a[n-1]+r-(a[0]+l)+1;//最大可能的答案
		int pos=upper_bound(c,c+n-1,sub)-c;
		ans-=(sum[n-2]-sum[pos-1]-(n-2-pos+1)*sub);
		if(fr){
			fr=0;cout<<ans<<endl;
		}
		else cout<<" "<<ans<<endl;
	}
}


E. Pavel and Triangles

time limit per test2 seconds memory limit per test256 megabytes

Pavel has several sticks with lengths equal to powers of two.

He has ?0a0 sticks of length 20=120=1, ?1a1 sticks of length 21=221=2, ..., ??−1an−1 sticks of length 2?−12n−1.

Pavel wants to make the maximum possible number of triangles using these sticks. The triangles should have strictly positive area, each stick can be used in at most one triangle.

It is forbidden to break sticks, and each triangle should consist of exactly three sticks.

Find the maximum possible number of triangles.Input

The first line contains a single integer ?n (1≤?≤3000001≤n≤300000) — the number of different lengths of sticks.

The second line contains ?n integers ?0a0, ?1a1, ..., ??−1an−1 (1≤??≤1091≤ai≤109), where ??ai is the number of sticks with the length equal to 2?2i.Output

Print a single integer — the maximum possible number of non-degenerate triangles that Pavel can make.
Examples
input

5 
1 2 2 2 2

output

3

input

3 
1 1 1

output

0

input

3 
3 3 3

output

3

Note

很显然对于每个三角形只会有等腰和等边两种情况,那么很显然可以用贪心策略,每次先用当前长度边和前面没匹配完的边组等腰,再有多的自己和自己组等边。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=(int)3e5+100;
const int mod=(int)1e9+7;
int main(){
	quickio;
	int n;cin>>n;
	ll ans=0,pre=0;
	while(n--){
		ll x;cin>>x;
		ll k=min(x/2,pre);
		x-=k*2;ans+=k;//等腰
		ans+=x/3;//等边
		pre-=k;pre+=x%3;
	}
	cout<<ans<<endl;
}

 

Subscribe
提醒
0 评论
Inline Feedbacks
View all comments