Codeforces Educational Round 64 (Div. 2)

A. Inscribed Figures

time limit per test1 second memory limit per test256 megabytes

The math faculty of Berland State University has suffered the sudden drop in the math skills of enrolling students. This year the highest grade on the entrance math test was 8. Out of 100! Thus, the decision was made to make the test easier.

Future students will be asked just a single question. They are given a sequence of integer numbers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an, each number is from 11to 33 and 𝑎𝑖≠𝑎𝑖+1ai≠ai+1 for each valid 𝑖i. The 𝑖i-th number represents a type of the 𝑖i-th figure:

  1. circle;
  2. isosceles triangle with the length of height equal to the length of base;
  3. square.

The figures of the given sequence are placed somewhere on a Cartesian plane in such a way that:

  • (𝑖+1)(i+1)-th figure is inscribed into the 𝑖i-th one;
  • each triangle base is parallel to OX;
  • the triangle is oriented in such a way that the vertex opposite to its base is at the top;
  • each square sides are parallel to the axes;
  • for each 𝑖i from 22 to 𝑛n figure 𝑖i has the maximum possible length of side for triangle and square and maximum radius for circle.

Note that the construction is unique for some fixed position and size of just the first figure.

The task is to calculate the number of distinct points (not necessarily with integer coordinates) where figures touch. The trick is, however, that the number is sometimes infinite. But that won’t make the task difficult for you, will it?

So can you pass the math test and enroll into Berland State University?Input

The first line contains a single integer 𝑛n (2≤𝑛≤1002≤n≤100) — the number of figures.

The second line contains 𝑛n integer numbers 𝑎1,𝑎2,…,𝑎𝑛a1,a2,…,an (1≤𝑎𝑖≤31≤ai≤3, 𝑎𝑖≠𝑎𝑖+1ai≠ai+1) — types of the figures.Output

The first line should contain either the word “Infinite” if the number of distinct points where figures touch is infinite or “Finite” otherwise.

If the number is finite than print it in the second line. It’s guaranteed that the number fits into 32-bit integer type.
Examplesinput

3
2 1 3

output

Finite
7

input

3
1 2 3

output

Infinite

Note

Here are the glorious pictures for the examples. Note that the triangle is not equilateral but just isosceles with the length of height equal to the length of base. Thus it fits into a square in a unique way.

The distinct points where figures touch are marked red.

In the second example the triangle and the square touch each other for the whole segment, it contains infinite number of points.

不愧是教育场,第一题就卡了我20分钟,还好1A了
首先考虑n=2的情况,发现答案只和两个数的和有关,这也是做下面一步的启发
n>2的情况,我们会神奇的发现只要出现2,3或者3,2相邻就不行,其他情况每加一个图形,答案就加上这个图形的编号和上一个的和;
但是要注意的是,如果出现了连续的3,1,2那么答案就要减1,因为此时有一个交点重叠了

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e4+100;
const int INF=0x3f3f3f3f;
int main(){
	int n,a[110];cin>>n;
	rep(i,1,n) scanf("%d",&a[i]);
	int ans=0;
	if(n==2){
		if(a[1]+a[2]==5){puts("Infinite");exit(0);}
		else printf("Finite\n%d\n",a[1]+a[2]);exit(0);
	}
	else{
		rep(i,2,n){
			if(a[i]+a[i-1]==5){puts("Infinite");exit(0);}
			ans+=a[i]+a[i-1];
		}
		int tem=0;
		rep(i,3,n) if(a[i-2]==3&&a[i-1]==1&&a[i]==2) tem++;
		ans-=tem;
		puts("Finite"); printf("%d\n",ans);
	}
}


B. Ugly Pairs

time limit per test1 second memory limit per test256 megabytes

You are given a string, consisting of lowercase Latin letters.

A pair of neighbouring letters in a string is considered ugly if these letters are also neighbouring in a alphabet. For example, string “abaca” contains ugly pairs at positions (1,2)(1,2) — “ab” and (2,3)(2,3) — “ba”. Letters ‘a’ and ‘z’ aren’t considered neighbouring in a alphabet.

Can you rearrange the letters of a given string so that there are no ugly pairs? You can choose any order of the letters of the given string but you can’t add any new letters or remove the existing ones. You can also leave the order the same.

If there are multiple answers, print any of them.

You also have to answer 𝑇T separate queries.Input

The first line contains a single integer 𝑇T (1≤𝑇≤1001≤T≤100) — the number of queries.

Each of the next 𝑇T lines contains string 𝑠s (1≤|𝑠|≤100)(1≤|s|≤100) — the string for the next query. It is guaranteed that it contains only lowercase Latin letters.

Note that in hacks you have to set 𝑇=1T=1.Output

Print 𝑇T lines. The 𝑖i-th line should contain the answer to the 𝑖i-th query.

If the answer for the 𝑖i-th query exists, then print such a rearrangment of letters of the given string that it contains no ugly pairs. You can choose any order of the letters of the given string but you can’t add any new letters or remove the existing ones. You can also leave the order the same.

If there are multiple answers, print any of them.

Otherwise print “No answer” for that query.
Exampleinput

4
abcd
gg
codeforces
abaca

output

cadb
gg
codfoerces
No answer

Note

In the first example answer “bdac” is also correct.

The second example showcases the fact that only neighbouring in alphabet letters are not allowed. The same letter is ok.

There are lots of valid answers for the third example.

set乱搞一下,构造新字符串的策略是,先把头尾拿过来,然后从剩下的字符中判断一下左右是否可以插入 哪边可以就插哪边
最后判断一下合不合理就可以了

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e4+100;
const int INF=0x3f3f3f3f;
int main(){
	int T;cin>>T;
	while(T--){
		string s;cin>>s;
		int len=s.length();
		set<char> c;int num[110]={0,};
		for(int i=0;i<len;++i){
			num[s[i]-'a']++;
			c.insert(s[i]);
		}
		if(c.size()==1) cout<<s<<endl;
		else{
			string ans;
			ans+=*c.begin();ans+=*(--c.end());
			int op=1;
			for(auto it=(++c.begin());it!=(--c.end());++it){
				if(op){
					if(abs(*it-ans[ans.length()-1])!=1){
						op=0; ans+=*it;
					}
					else{
						op=1; ans=*it+ans;
					}
				}
				else{
					if(abs(*it-ans[0])!=1){
						op=1; ans=*it+ans;
					}
					else {
						op=0; ans+=*it;
					}
				}
			}
			//cout<<ans<<endl;
			int flag=0;
			for(int i=1;i<ans.length();++i){
				if(abs(ans[i]-ans[i-1])==1) {flag=1;break;}
			}
			if(flag) puts("No answer");
			else{
				for(int i=0;i<ans.length();++i)
					rep(j,1,num[ans[i]-'a']) cout<<ans[i];
				puts("");
			}
		}
	}
	return 0;
}

C. Match Points

time limit per test2 seconds memory limit per test256 megabytes

You are given a set of points 𝑥1×1, 𝑥2×2, …, 𝑥𝑛xn on the number line.

Two points 𝑖i and 𝑗j can be matched with each other if the following conditions hold:

  • neither 𝑖i nor 𝑗j is matched with any other point;
  • |𝑥𝑖−𝑥𝑗|≥𝑧|xi−xj|≥z.

What is the maximum number of pairs of points you can match with each other?Input

The first line contains two integers 𝑛n and 𝑧z (2≤𝑛≤2⋅1052≤n≤2⋅105, 1≤𝑧≤1091≤z≤109) — the number of points and the constraint on the distance between matched points, respectively.

The second line contains 𝑛n integers 𝑥1×1, 𝑥2×2, …, 𝑥𝑛xn (1≤𝑥𝑖≤1091≤xi≤109).Output

Print one integer — the maximum number of pairs of points you can match with each other.
Examplesinput

4 2
1 3 3 7

output

2

input

5 5
10 9 5 8 7

output

1

Note

In the first example, you may match point 11 with point 22 (|3−1|≥2|3−1|≥2), and point 33 with point 44 (|7−3|≥2|7−3|≥2).

In the second example, you may match point 11 with point 33 (|5−10|≥5|5−10|≥5).

显然,匹配的最大答案是n/2,既所有都匹配;
并且,假设有a<b<c<d,如果(a,b)和(c,d)都匹配,那么显然(a,c)和(b,d)也都匹配;
反之,如果(a,c)和(b,d)匹配,那(a,b)和(c,d)未必匹配;
因此,我们搞两个指针,然后把序列分成左右两部分,对于右区间的每个数,在左区间内找到最大的可以和它匹配的数,扫完就是答案了;


数组左半边和右半边匹配完之后。不可能在左半边还能找出两个数能够匹配的。

证明:假设左半边还存在两个数a和b能够匹配。因为数组左右两边的个数差小于等于1。那么右半边肯定存在c能够和a匹配。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int INF=0x3f3f3f3f;
int a[maxn];
int main(){
	int n,z;cin>>n>>z;
	rep(i,1,n) scanf("%d",&a[i]); sort(a+1,a+1+n);
	int p=(n+1)>>1,l=p,r=n,ans=0;
	while(r>p&&l){
		if(a[r]-a[l]>=z) ans++,l--,r--;
		else l--;
	}
	printf("%d\n",ans);
	return 0;
}


D. 0-1-Tree

time limit per test2 seconds memory limit per test256 megabytes

You are given a tree (an undirected connected acyclic graph) consisting of 𝑛n vertices and 𝑛−1n−1 edges. A number is written on each edge, each number is either 00 (let’s call such edges 00-edges) or 11 (those are 11-edges).

Let’s call an ordered pair of vertices (𝑥,𝑦)(x,y) (𝑥≠𝑦x≠y) valid if, while traversing the simple path from 𝑥x to 𝑦y, we never go through a 00-edge after going through a 11-edge. Your task is to calculate the number of valid pairs in the tree.Input

The first line contains one integer 𝑛n (2≤𝑛≤2000002≤n≤200000) — the number of vertices in the tree.

Then 𝑛−1n−1 lines follow, each denoting an edge of the tree. Each edge is represented by three integers 𝑥𝑖xi, 𝑦𝑖yi and 𝑐𝑖ci (1≤𝑥𝑖,𝑦𝑖≤𝑛1≤xi,yi≤n, 0≤𝑐𝑖≤10≤ci≤1, 𝑥𝑖≠𝑦𝑖xi≠yi) — the vertices connected by this edge and the number written on it, respectively.

It is guaranteed that the given edges form a tree.Output

Print one integer — the number of valid pairs of vertices.
Exampleinput

7
2 1 1
3 2 0
4 2 1
5 2 0
6 7 1
7 2 1

output

34

Note

The picture corresponding to the first example:

看似很难,但是nlg(n)的算法可以莽过去;
对于答案肯定只有三种可能,一串0(00000),一串1(111111),或者一串0接着一串1(000001111);
那么用两个并查集存0边的联通块和1边的联通块,然后对于情况1和2的贡献就是每个联通块个数tot*(tot-1);
对于情况3,肯定可以找到一个点,它的左边全都是0,右边都是1,对于这样的点的贡献就是(tot[0][find(i,0)]-1)*(tot[1][find(i,1)]-1)

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
const int INF=0x3f3f3f3f;
ll pre[2][maxn],tot[2][maxn],n;
void init(){rep(i,0,n) pre[0][i]=pre[1][i]=i,tot[0][i]=tot[1][i]=1;}
ll find(ll x,int op){return x==pre[op][x]?x:pre[op][x]=find(pre[op][x],op);}
void join(ll x,ll y,int op){
	x=find(x,op);y=find(y,op);
	if(x!=y) pre[op][x]=y,tot[op][y]+=tot[op][x];
}
int main(){
	cin>>n;init();
	rep(i,2,n){
		ll u,v;int w;scanf("%lld%lld%d",&u,&v,&w);
		join(u,v,w);
	}
	ll ans=0;
	rep(i,1,n){
		rep(j,0,1) if(pre[j][i]==i) ans+=(tot[j][i]-1)*tot[j][i];
		ans+=(tot[0][find(i,0)]-1)*(tot[1][find(i,1)]-1);
	}
	printf("%lld\n",ans);
}

E. Special Segments of Permutation

time limit per test2 seconds memory limit per test512 megabytes

You are given a permutation 𝑝p of 𝑛n integers 11, 22, …, 𝑛n (a permutation is an array where each element from 11 to 𝑛n occurs exactly once).

Let’s call some subsegment 𝑝[𝑙,𝑟]p[l,r] of this permutation special if 𝑝𝑙+𝑝𝑟=max𝑖=𝑙𝑟𝑝𝑖pl+pr=maxi=lrpi. Please calculate the number of special subsegments.Input

The first line contains one integer 𝑛n (3≤𝑛≤2⋅1053≤n≤2⋅105).

The second line contains 𝑛n integers 𝑝1p1, 𝑝2p2, …, 𝑝𝑛pn (1≤𝑝𝑖≤𝑛1≤pi≤n). All these integers are pairwise distinct.Output

Print the number of special subsegments of the given permutation.
Examplesinput

5
3 4 1 5 2

output

2

input

3
1 3 2

output

1

Note

Special subsegments in the first example are [1,5][1,5] and [1,3][1,3].

The only special subsegment in the second example is [1,3][1,3].

启发式合并,先对每个数跑一遍单调栈,找到每个位置的l,r区间,然后在左右区间中较短的那个中枚举每个数,看看另一个区间中有没有需要的数,更新答案
由于每次做多枚举当前区间一半的数,相当于二分,所以复杂度是n lg(n)的

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)2e5+100;
int n,a[maxn];
int l[maxn],r[maxn],pos[maxn];
ll ans=0;
void work(int x){
	int L,R,pl,pr;
	if(x-l[x]<r[x]-x){
		L=l[x];R=x-1;pl=x+1;pr=r[x];
	}
	else{
		L=x+1;R=r[x];pl=l[x];pr=x-1;
	}
	rep(i,L,R){
		int t=a[x]-a[i];
		if(pl<=pos[t]&&pos[t]<=pr) ans++;
	}
}
int main(){
	cin>>n; rep(i,1,n) scanf("%d",&a[i]),pos[a[i]]=l[i]=r[i]=i;
	a[0]=a[n+1]=n+1;
	rep(i,1,n) while(a[l[i]-1]<a[i]) l[i]=l[l[i]-1];
	dep(i,n,1) while(a[r[i]+1]<a[i]) r[i]=r[r[i]+1];
	rep(i,1,n) work(i);
	printf("%lld\n",ans);
}

 

发表评论,支持MarkDown语法