3-й этап Республиканской олимпиады по информатике 2021-2022, 1 тур

Есеп B. AB

Ограничение по времени:

1 second

Ограничение по памяти:

256 megabytes

Сізге 'a' және 'b' әріптерінен тұратын $s$ және $t$ екі сөзі берілген. \textbf {$s$ сөзінде көрші бірдей әріптер жоқ}. Сіз $s$-ке тең $t$-ның ең көп қиылыспайтын ішкі тізбектерін таңдағыңыз келеді. Ішкі тізбек - - - бұл сөзден бірнеше (мүмкін нөл) элементтерін алып тастау арқылы алуға болатын сөз тізбегі. Таңдауға болатын ең көп ішкі тізбектердің санын табыңыз.

Оқу форматы

Бірінші жолда $s$ сөзі берілген ($1 <= |s| <= 4$). $s$ cөзінде көрші бірдей әріптер жоқ екеніне кепілдік беріледі. Екінші жолда $t$ сөзі берілген ($1 <= |t| <= 10^5$).

Жазу форматы

Бір бүтін санды — сіз таңдай алатын ішкі тізбектердің ең көп санын шығарыңыз.

Система оценки

Есеп $7$ бөлімнен тұрады:

1. Есептің шартында берілген тесттер. $0$ ұпайға бағаланады.
2. $|s| = 1$. $11$ ұпайға бағаланады.
3. $|s| = 2$. $14$ ұпайға бағаланады.
4. $|s| = 3$. $20$ ұпайға бағаланады.
5. $|s| = 4$, $|t| <= 50$. $18$ ұпайға бағаланады.
6. $|s| = 4$, $|t| <= 300$. $12$ ұпайға бағаланады.
7. $|s| = 4$, $|t| <= 10^5$. $25$ ұпайға бағаланады.

Примеры:

Вход

ab
abbaba

Ответ

2

Вход

  
aba
ababaa

Ответ

2

Түсініктеме

Екінші мысалда {1, 2, 5} және {3, 4, 6} индекстерімен қиылыспайтын екі тізбекті таңдауға болады. ( Aibar Kuanyshbay )

Комментарий/решение

Полное решение

кодты корсету/жасыру

#include<bits/stdc++.h>
#define ll            long long
#define pb            push_back
#define F             first
#define S             second
#define mk            make_pair
#define skip          continue;
#define ld            long double
#define pf			  push_front
using namespace std;
const int L=1e7+11;
const int N=2e3;
const ll mod=1000000007;
const double pi=3.14159265359;
void solve(){
	string s,t;
	cin>>s>>t;
	if(s.size()==1){
		int ans=0;
		for(int i=0; i<t.size(); i++){
			if(s[0]==t[i]){
				ans++;
			}
		}
		cout<<ans<<endl;
	}else if(s.size()==2 || s.size()==4){
		int ans=0,k=0,sum=0;
		if(s[0]=='a'){
			for(int i=0; i<t.size(); i++){
				if(t[i]=='b'){
					sum++;
				}
			}
			for(int i=0; i<t.size(); i++){
				if(t[i]=='b'){
					if(k)k--;
					else sum--;
				}else{
					if(sum>0){
						ans++;sum--;k++;
					}
				}
			}if(s.size()==4){
				ans/=2;
			}cout<<ans<<endl;
		}else{
			for(int i=0; i<t.size(); i++){
				if(t[i]=='a'){
					sum++;
				}
			}
			for(int i=0; i<t.size(); i++){
				if(t[i]=='a'){
					if(k)k--;
					else sum--;
				}else{
					if(sum>0){
						ans++;sum--;k++;
					}
				}
			}if(s.size()==4){
				ans/=2;
			}cout<<ans<<endl;
		}
	}else{
		int ans=0,k=0,sum=0;
		if(s[0]=='a'){
			for(int i=0; i<t.size(); i++){
				if(t[i]=='a')sum++;
				else k++;
			}
			cout<<min(sum/2,k)<<endl;
		}else{
			for(int i=0; i<t.size(); i++){
				if(t[i]=='b')sum++;
				else k++;
			}
			cout<<min(sum/2,k)<<endl;
		}
	}
}
/*
*/
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", " w", stdout);
int tt=1;
//cin>>tt;
while(tt--){
	solve();
}
}

C++

Copy