Educational Codeforces Round 132 (Rated for Div. 2)【A~C】

A - Three Doors

The question

​ There are three doors , Each door has a matching key . The key to a door will be given initially , And put the other two keys behind the two doors , Please open all three doors

Answer key

​ Jump every time according to the currently available door , When you meet $0$ Quit when you're on the road , Judge whether three doors have been opened at present .

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
ll _;
/*-------------------------------------------------*/
/*-------------------------------------------------*/
ll n,m;
void solve(){
    
	cin>>n;
	int a[5],cnt=1;
	for(int i=1;i<=3;i++){
    
		cin>>a[i];
	}
	while(a[n]){
    
		n=a[n];
		cnt++;
	}
	
	if(cnt==3)puts("YES");
	else puts("NO");
}
int main(){
    
	cin>>_;while(_--)
    solve();
    return 0;
}

B - Also Try Minecraft

The question

​ Give a length of $n$ Array of ,$a_i$ Express $i$ The floor height of the location . You can move one unit left or right at a time , If you move from high to low, you will get fall damage with a value of height difference , Seek from $s$ Move to $t$ Get fall damage .

Answer key

​ Because the starting point can be larger than the ending point , It can also be smaller than the end , So find the sum of two prefixes , One is from left to right $a[i]-a[i-1]$ The prefix of and the other is from left to right $a[i-1]-a[i]$ And , Because in this way, the starting point is greater than the end point to exchange , In this way, we can find two cases according to the same logic .

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
ll _;
/*-------------------------------------------------*/
/*-------------------------------------------------*/
ll n,m;
ll a[N];
ll s1[N];//l->r
ll s2[N];//r->l
void solve(){
    
	cin>>n>>m;
	for(int i=1;i<=n;i++){
    
		cin>>a[i];
	}
	for(int i=1;i<n;i++){
    
		ll t1=max(0ll,a[i]-a[i+1]);
		ll t2=max(0ll,a[i+1]-a[i]);
		s1[i]=s1[i-1]+t1;
		s2[i]=s2[i-1]+t2;
	}
	while(m--){
    
		int s,t;
		cin>>s>>t;
		if(s<=t){
    
			cout<<s1[t-1]-s1[s-1]<<endl;
		}else{
    
			swap(s,t);
			cout<<s2[t-1]-s2[s-1]<<endl;
		}
	}
}
int main(){
    
	//cin>>_;while(_--)
    solve();
    return 0;
}

C - Recover an RBS

The question

​ Given a by " $?$ “,” $($ “,” $)$ " Composed string . among $?$ It can be converted to left bracket or right bracket , Determine whether the current string is a unique match .

• Unique match ： If it happens $?$ It can be either a left bracket or a right bracket , This is not the only match .

Answer key

​ This question is mainly to determine how to be unique . Here I give three examples ：

• $(??)$
• $(??())?)$
• $()??$

There are several rules when matching ：

（1）$)$ Priority matching $($ If it doesn't exist $($ Just match $?$.

（2）$($ All match perfectly and only one is left $?$ Will this $?$ Convert to $($.

（3） You can find , If the left and right sides match $?$ The rest of , This is not the only .
【 Just went to have a look again , It is found that there must be at least one match in the title, so there will be no “((???((” Data like this （ I thought I was going to be hack 了 ）】

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
ll _;
/*-------------------------------------------------*/
/*-------------------------------------------------*/
ll n,m;
void solve(){
    
	string str;
	cin>>str;
	int cntl=0,cnt=0;
	for(int i=0;i<str.size();i++){
    
		if(str[i]=='('){
    
			cntl++;
		}else if(str[i]==')'){
    
			if(!cntl){
    
				cnt--;
			}else{
    
				cntl--;
			}
		}else{
    
			cnt++;
		}
		if(cnt==1&&!cntl){
    
			cnt--;
			cntl++;
		}
	}
	cnt-=cntl;
	if(!cnt)puts("YES");
	else puts("NO");
}
int main(){
    
	cin>>_;while(_--)
    solve();
    return 0;
}