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,…,𝑥2×1,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,𝑦2×1,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;
}

 

发表评论,支持MarkDown语法