Задача 6058. Источник: Поляков. Задание КИМ 24
Текстовый файл 24-247.txt состоит не более чем из 106 символов и содержит только латинские заглавные буквы A...Z. Найдите в файле самую длинную цепочку одинаковых букв, стоящих рядом. Запишите в ответе, сколько раз буква, образующая эту цепочку, встречается в соответствующей строке. Если в файле есть несколько строк с цепочками одинаковой максимальной длины, нужно взять ту, где общее количество этих букв больше.
Пример. Пусть в файле находятся две строки:
ABCAAABCA
ABBBCDAEFB
Здесь две цепочки длиной 3: AAA в первой строке и BBB во второй. Но буква A в первой строке всего встречается 5 раз, а буква B во второй строке – 4 раза. Выбираем большее из этих двух значений. Ответ: 5.
Решение
В данной задаче следует учитывать, что в одной строке может оказаться несколько букв, имеющих цепочку одинаковой максимальной длины, а потому помимо максимальной длины следует хранить список букв, которые имеют цепочку такой длины. Обрабатываем файл построчно. Для каждой строки находим наибольшую цепочку подряд идущих одинаковых символов и список букв, имеющих такую цепочку. Обрабатывая буквы из списка, находим, какая из них встречается в строке чаще. Результат строки сравниваем с промежуточным результатом файла и обновляем значения, если найдены новые максимальные значения.
Python
f = open('24-247.txt')
mx = 0
mxn = 0
for s in f:
c = [s[0]]
k = 1
m = 1
for i in range(1, len(s)):
if s[i] == s[i - 1]:
k += 1
if k > m:
m = k
c = [s[i]]
elif k == m:
c.append(s[i])
else:
k = 1
if m > mxn:
mxn = m
for j in c:
m = max(m, s.count(j))
mx = m
elif m == mxn:
for j in c:
mx = max(mx, s.count(j))
print(mx)
PascalABC
var
i, max, maxn, m, k: Integer;
s: String;
c: Array of Char;
j: Char;
f: TEXT;
begin
Assign(f, '24-247.txt');
Reset(f);
max := 0;
maxn := 0;
while not eof(f) do
begin
Readln(f, s);
c := Arr(s[1]);
k := 1;
m := 1;
for i := 2 to s.Length do
if s[i] = s[i - 1] then
begin
k := k + 1;
if k > m then
begin
m := k;
c := Arr(s[i]);
end
else if k = m then
c := c + Arr(s[i]);
end
else
k := 1;
if m > maxn then
begin
maxn := m;
foreach j in c do
begin
k := 0;
for i := 1 to s.Length do
if s[i] = j then
k := k + 1;
if k > m then
m := k;
end;
max := m;
end
else if m = maxn then
begin
foreach j in c do
begin
k := 0;
for i := 1 to s.Length do
if s[i] = j then
k := k + 1;
if k > max then
max := k;
end;
end;
end;
Writeln(max);
end.
C++
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int main()
{
ifstream f;
f.open("24-247.txt");
string s;
int max = 0, maxn = 0;
while (f >> s)
{
vector<char> c;
int k = 1, m = 1;
for (int i = 1; i < s.length(); i++)
if (s[i] == s[i - 1])
{
k++;
if (k > m)
{
m = k;
c.clear();
c.push_back(s[i]);
}
else if (k == m)
c.push_back(s[i]);
}
else
k = 1;
if (m > maxn)
{
maxn = m;
for (int i = 0; i < c.size(); i++)
{
k = 0;
for (int j = 0; j < s.length(); j++)
if (s[j] == c[i])
k++;
if (k > m)
m = k;
}
max = m;
}
else if (m == maxn)
{
for (int i = 0; i < c.size(); i++)
{
k = 0;
for (int j = 0; j < s.length(); j++)
if (s[j] == c[i])
k++;
if (k > max)
max = k;
}
}
}
cout << max << endl;
}
Ответ
29