кто знает програмирование на языке с++ решите задачу
A. Краучиха
ограничение по времени на тест1 секунда
ограничение по памяти на тест256 мегабайт
вводстандартный ввод
выводстандартный вывод
Давным давно в армии служили два солдата, Краучиха и его босс (К сожалению, по сей день нам не известно настоящая имя босса). Однажды босс дал Краучихе задание и строку (обозначим как S) из строчных букв чтобы найти красивый хэндл для регистрации на Codeforces. Хэндл называется красивым если он является подстрокой S и содержит максимальное количество различных букв. Краучиха как верный помощник решил найти красивый хэндл с минимальной длиной, но тут у него появились проблемы: он оказывается не умеет считать. Помогите ему найти минимальную длину красивого хэндла, тогда возможно он вам тоже поможет взять хорошое место на олимпиаде...
Входные данные
В первой и единственной строке дана строка S из строчных латинских букв. (1≤|S|≤5∗105)
Выходные данные
Выведите минимальную длину красивого хэдла
Система оценки
В этой задаче 4 сабтасков
1. (1≤|S|≤100). 21 баллов
2. (1≤|S|≤1000). 17 баллов
3. S состоит только из букв а, b. S ∈ {a, b}. 19 баллов
4. (1≤|S|≤5∗105). 43 баллов
Примеры
входные данные
maxbey
выходные данные
6
входные данные
abacaba
выходные данные
3
входные данные
accdcd
выходные данные
4
A. Краучиха
ограничение по времени на тест1 секунда
ограничение по памяти на тест256 мегабайт
вводстандартный ввод
выводстандартный вывод
Давным давно в армии служили два солдата, Краучиха и его босс (К сожалению, по сей день нам не известно настоящая имя босса). Однажды босс дал Краучихе задание и строку (обозначим как S) из строчных букв чтобы найти красивый хэндл для регистрации на Codeforces. Хэндл называется красивым если он является подстрокой S и содержит максимальное количество различных букв. Краучиха как верный помощник решил найти красивый хэндл с минимальной длиной, но тут у него появились проблемы: он оказывается не умеет считать. Помогите ему найти минимальную длину красивого хэндла, тогда возможно он вам тоже поможет взять хорошое место на олимпиаде...
Входные данные
В первой и единственной строке дана строка S из строчных латинских букв. (1≤|S|≤5∗105)
Выходные данные
Выведите минимальную длину красивого хэдла
Система оценки
В этой задаче 4 сабтасков
1. (1≤|S|≤100). 21 баллов
2. (1≤|S|≤1000). 17 баллов
3. S состоит только из букв а, b. S ∈ {a, b}. 19 баллов
4. (1≤|S|≤5∗105). 43 баллов
Примеры
входные данные
maxbey
выходные данные
6
входные данные
abacaba
выходные данные
3
входные данные
accdcd
выходные данные
4
More Questions From This User See All
Answers & Comments
Ответ:
Ах ты ж мелкий, сам КБО написать не можешь?) 19 баллов - это приговор.
Объяснение:
#include <bits/stdc++.h>
using namespace std;
int cnt[30], kol;
string s;
bool check (int mid) {
int x[30]{}, y = 0;
for (int i = 0; i < mid; i++) {
x[s[i] - 'a' + 1]++;
if (x[s[i] - 'a' + 1] == 1)
y++;
}
int l, r = mid - 1;
for (l = 0; r < s.size();) {
if (y == kol)
return true;
if (x[s[l] - 'a' + 1] == 1)
y--;
x[s[l] - 'a' + 1]--;
l++;
r++;
if (x[s[r] - 'a' + 1] == 0)
y++;
x[s[r] - 'a' + 1]++;
}
return false;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> s;
for (auto it : s)
cnt[it - 'a' + 1]++;
for (int i = 1; i <= 26; i++) {
if (cnt[i] > 0)
kol++;
}
int l = 0, r = s.size();
while (r - l > 1) {
int mid = l + (r - l) / 2;
if (check (mid))
r = mid;
else
l = mid;
}
cout << r;
}