Задача 6057. Источник: Поляков. Задание КИМ 24
Текстовый файл 24-247.txt состоит не более чем из 106 символов и содержит только латинские заглавные буквы A...Z. Найдите в файле самую длинную цепочку одинаковых букв, стоящих рядом. Запишите в ответе, сколько раз буква, образующая эту цепочку, встречается в соответствующей строке. Если в файле есть несколько строк с цепочками одинаковой максимальной длины, нужно взять ту, где общее количество этих букв меньше.
Пример. Пусть в файле находятся две строки:
ABCAAABCA
ABBBCDAEFB
Здесь две цепочки длиной 3: AAA в первой строке и BBB во второй. Но буква A в первой строке всего встречается 5 раз, а буква B во второй строке – 4 раза. Выбираем меньшее из этих двух значений. Ответ: 4.
Решение
Обратите внимание, что несколько цепочек одинаковой максимальной длины может быть даже в одной строке. По этой причине нужно сохранять не одну букву, для которой такая цепочка обнаружена, а список букв. Считываем строки из файла и анализируем каждую. Находим максимальную длину цепочки и список букв, которые такую цепочку содержат. Среди найденных букв из списка находим ту, которая встречается в строке реже. Полученные данные сравниваем с переменными, хранящими результат для всего файла.
Python
f = open('24-247.txt')
mn = 1000000
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
m = len(s)
for j in c:
m = min(m, s.count(j))
mn = m
elif m == mxn:
for j in c:
mn = min(mn, s.count(j))
print(mn)
PascalABC
var
i, min, maxn, m, k: Integer;
s: String;
c: Array of Char;
j: Char;
f: TEXT;
begin
Assign(f, '24-247.txt');
Reset(f);
min := 1000000;
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;
m := s.Length;
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;
min := 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 < min then
min := k;
end;
end;
end;
Writeln(min);
end.
C++
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int main()
{
ifstream f;
f.open("24-247.txt");
string s;
int min = 1000000, 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;
m = s.length();
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;
}
min = 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 < min)
min = k;
}
}
}
cout << min << endl;
}
Ответ
22