Республиканская олимпиада по информатике, 2015 год, 9 класс
Задача B. Буквы
Задается строка $S$, состоящая из строчных букв английского алфавита. Найдите в ней подстроку наименьшей длины, в которую входят ровно $K$ различных букв, и выведите ее длину.Входные данные
В первой строке входного файла задается одна строка $S$, состоящая из строчных букв английского алфавита. Во второй строке задается одно целое положительное число $K$ ($ 1\le K \le 26$).Выходные данные
Выведите ответ к задаче или -1, если такой подстроки не существует.Примеры
aaabbccc 3
Ответ:
4
Оценивание:
Данная задача содержит три подзадачи:длина строки $S \le 100$. Оценивается в $20$ баллов.
длина строки $S \le 5000$. Оценивается в $30$ баллов.
длина строки $S \le 10^5$. Оценивается в $50$ баллов.
Каждая следующая подзадача оценивается только при прохождении всех предыдущих. ( Ержан Уткелбаев )
Комментарий/решение:
#include <iostream>
using namespace std;
int main() {
string s;
int k;
cin >> s;
cin >> k;
if(k == s.size()){
cout << k;
return 0;
}
int a[s.size()+1];
a[0] = 1;
for(int i = 1; i < s.size(); i++){
if(s[i] == s[i - 1]){
a[i] = a[i - 1];
}else{
a[i] = a[i - 1] + 1;
}
}
int mn = s.size();
int j;
for(int i = 0; i < s.size(); i++){
if(a[i] >= k){
j = i;
while(a[j] != a[i] - k + 1) {
j--;
}
if (mn > i - j + 1) {
mn = i - j + 1;
}
}
if (mn == k) {
cout << mn;
return 0;
}
}
cout << mn;
return 0;
}
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.