Задача 6610. Источник: Поляков. Задание КИМ 24

Страница задачи 6610

Решение

Создадим массив, из пяти элементов, где будем сохранять пять последних позиций комбинаций SOLO. Встретив шестую комбинацию, анализируем количество уникальных цифр от самой первой сохраненной позиции до текущей. Для этого создадим массив логического типа из 10 элементов, где значение true будет для цифр, которые еще не встречались, а false - для цифр, которые уже встретились и посчитаны. Встретив цифру, которая еще не встречалась, увеличиваем счетчик. Если количество уникальных цифр 5 и более, анализируем длину подстроки на возможный максимум. Обратите внимание, что три последних символа первой комбинации SOLO и три первых символа текущей комбинации входят в подстроку:

...SOLOA5T3BSOLOHF75GSOLOY5J2QSOLOKAV0LSOLO5R9NXISOLO...
   ^        ^        ^        ^        ^         ^
 last[0]  last[1]  last[2]  last[3]  last[4]     i

После цикла надо обязательно проанализировать подстроку от первой комбинации SOLO и до конца файла, т.к. этот фрагмент не будет обработан в цикле, а решение может оказаться в нем.

Возможно и более эффективное решение, когда во время посимвольной обработки фиксируется наличие цифр между каждой парой комбинаций SOLO или комбинацией SOLO и началом/концом файла, а потом анализом пяти массивов определяется общее количество уникальных цифр, но объем кода такого решения больше, а текущее решение даже на Python находит ответ за несколько секунд. К более эффективному решению имеет смысл прибегать в случае схожей олимпиадной задачи с обработкой файлов в десятки или сотни мегабайт.

Python

s = open('24-262.txt').readline()
last = [-1] * 5
mx = 0
for i in range(len(s)):
    if s[i: i+ 4] == 'SOLO':
        d = [True] * 10
        k = 0
        for j in range(last[0] + 1,  i):
            if s[j].isdigit() and d[int(s[j])]:
                k += 1
                d[int(s[j])] = False
        if k > 4:
            mx = max(mx, i - last[0] + 2)
        del last[0]
        last.append(i)
d = [True] * 10
k = 0
for j in range(last[0] + 1,  len(s)):
    if s[j].isdigit() and d[int(s[j])]:
        k += 1
        d[int(s[j])] = False
if k > 4:
    mx = max(mx, len(s) - 1 - last[0])
print(mx)

PascalABC

var
    i, j, max, k: Integer;
    s: String;
    last: Array [0..4] of Integer = (0, 0, 0, 0, 0);
    d: Array of Boolean = new Boolean[10];
    f: TEXT;
begin
    Assign(f, '24-262.txt');
    Reset(f);
    Readln(f, s);
    max := 0;
    for i := 1 to s.Length do
        if (i < s.Length - 2) and (s[i:i + 4] = 'SOLO') then
        begin
            d.Fill(True);
            k := 0;
            for j := last[0] + 1 to i - 1 do
                if (s[j].IsDigit) and d[ord(s[j]) - 48] then
                begin
                    k := k + 1;
                    d[ord(s[j]) - 48] := False;
                end;
            if (k > 4) and (i - last[0] + 2 > max) then
                max := i - last[0] + 2;
            for j := 0 to 3 do
                last[j] := last[j + 1];
            last[4] := i;
        end;
    d.Fill(True);
    k := 0;
    for j := last[0] + 1 to s.Length do
        if s[j].IsDigit and d[ord(s[j]) - 48] then
        begin
            k := k + 1;
            d[ord(s[j]) - 48] := False;
        end;
    if (k > 4) and (s.Length - 1 - last[0] > max) then
        max := s.Length - 1 - last[0];
    Writeln(max);
end.

C++

#include <iostream>
#include <fstream>
using namespace std;
int main()
{
    ifstream f;
    f.open("24-262.txt");
    string s;
    f >> s;
    int max = 0;
    int last[5] = { -1, -1, -1, -1, -1 };
    for (int i = 0; i < s.length(); i++)
        if (s.substr(i, 4) == "SOLO")
        {
            bool d[10];
            for (int j = 0; j < 10; j++)
                d[j] = true;
            int k = 0;
            for (int j = last[0] + 1; j < i; j++)
                if (s[j] >= '0' && s[j] <= '9' && d[(int)s[j] - 48])
                {
                    k++;
                    d[(int)s[j] - 48] = false;
                }
            if (k > 4 && i - last[0] + 2 > max)
                max = i - last[0] + 2;
            for (int j = 0; j < 4; j++)
                last[j] = last[j + 1];
            last[4] = i;
        }
    bool d[10];
    for (int j = 0; j < 10; j++)
        d[j] = true;
    int k = 0;
    for (int j = last[0] + 1; j < s.length(); j++)
        if (s[j] >= '0' && s[j] <= '9' && d[(int)s[j] - 48])
        {
            k++;
            d[(int)s[j] - 48] = false;
        }
    if (k > 4 && s.length() - 1 - last[0] + 2 > max)
        max = s.length() - 1 - last[0] + 2;
    cout << max << endl;
}

Ответ

431

Отправить замечание по решению