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

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

Решение

Условие неполной тройки существенно усложняет логику анализа текущего символа. Если это первый символ подстроки, то это может быть A или D. Если это второй символ подстроки, то перед D может стоять любой из двух символов, а перед A должен стоять только D. Если это любой последующий символ, то перед символом A может стоять только пара DD, а перед символом D может стоять AD или DA. Усложняется и логика инициализации счетчика при прерывании цепочки. Если текущий символ D (при прерывании цепочки, перед ним обязательно будет D) или текущий символ A и перед ним стоит D, то счетчик равен двум. Если текущий символ А, но перед ним нет D, то счетчик равен одному. В противном случае, счетчик равен нулю.

Операции со срезами в программах на Python и PascalABC могут быть заменены на посимвольный анализ, аналогичный программе на C++.

Python

s = open("24-238.txt").readline()
k = 0
mx = 0
for i in range(len(s)):
    if (s[i] == "A" and (k == 0 or k == 1 and s[i - 1] == "D" or
                         k > 1 and s[i - 2:i] == "DD") or
        s[i] == "D" and (k < 2 or k > 1 and
                         (s[i - 2:i] == "AD" or s[i - 2:i] == "DA"))):
        k += 1
        mx = max(mx, k)
    elif i > 0 and (s[i] == "D" or s[i - 1:i + 1] == "DA"):
        k = 2
    elif s[i] == "A":
        k = 1
    else:
        k = 0
print(mx)

PascalABC

var
    i, k, max: Integer;
    s: String;
    f: TEXT;
begin
    Assign(f, '24-238.txt');
    Reset(f);
    Readln(f, s);
    k := 0;
    max := 0;
    for i := 1 to s.Length do
    begin
        if ((s[i] = 'A') and ((k = 0) or (k = 1) and (s[i - 1] = 'D') or
                              (k > 1) and (s[i - 2:i] = 'DD')) or
            (s[i] = 'D') and ((k < 2) or (k > 1) and
                              ((s[i - 2:i] = 'AD') or (s[i - 2:i] = 'DA')))) then
        begin
            k := k + 1;
            if max < k then
                max := k;
        end
        else if (i > 1) and ((s[i] = 'D') or (s[i - 1:i + 1] = 'DA')) then
            k := 2
        else if s[i] = 'A' then
            k := 1
        else
            k := 0
    end;
    Writeln(max);
end.

C++

#include <iostream>
#include <fstream>
using namespace std;
int main()
{
    ifstream f;
    f.open("24-238.txt");
    string s;
    f >> s;
    int k = 0, max = 0;
    for (int i = 0; i < s.length(); i++)
    {
        if ((s[i] == 'A' && (k == 0 or k == 1 && s[i - 1] == 'D' ||
                             k > 1 && s[i - 1] == 'D' && s[i - 2] == 'D') ||
            s[i] == 'D' && (k < 2 || k > 1 && (s[i - 1] == 'A' && s[i - 2] == 'D' ||
                                               s[i - 1] == 'D' && s[i - 2] == 'A'))))
        {
            k++;
            if (max < k)
                max = k;
        }
        else if (i > 0 && (s[i] == 'D' || s[i - 1] == 'D' && s[i] == 'A'))
            k = 2;
        else if (s[i] == 'A')
            k = 1;
        else
            k = 0;
    }
    cout << max << endl;
}

Ответ

99

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