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

Задача B. AB

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

1 секунда

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

256 мегабайт

Вам даны две строки $s$ и $t$, которые состоят из букв 'a' и 'b'. В строке $s$ нет соседних одинаковых букв. Вы хотите выбрать наибольшее количество непересекающихся подпоследовательностей $t$, которые равны $s$. Подпоследовательность — это такая последовательность строки, которая может быть получена удалением нескольких (возможно ноль) элементов из этой строки. Найдите максимальное количество подпоследовательностей, которое вы сможете выбрать.

Формат входного файла

Первая строка входных данных содержит одну строку s ($1 <= |s| <= 4$). Гарантируется, что в строке $s$ нет соседних одинаковых букв. Вторая строка входных данных содержит одну строку 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

Замечание

Во втором примере можно выбрать две непересекающихся последовательности c индексами {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();
}
}