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:
- circle;
- isosceles triangle with the length of height equal to the length of base;
- 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 ?1x1, ?2x2, ..., ??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 ?1x1, ?2x2, ..., ??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);
}
