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

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

Решение

Создадим массив/список из 150 элементов, где будем сохранять последние 150 позиций буквы Y. Пока этот массив не заполнится, продолжаем подсчет длины строки. Когда массив заполнится, длина следующей строки отсчитывается после самой дальней сохраненной позиции Y.

Python

s = open('24-263.txt').readline()
k = 0
mx = 0
last = [-1] * 150
for i in range(len(s)):
    if s[i] == 'Y':
        if last[0] == -1:
            k += 1
            mx = max(mx, k)
        else:
            k = i - last[0]
        del last[0]
        last.append(i)
    else:
        k += 1
        mx = max(mx, k)
print(mx)

PascalABC с использованием статического массива

var
    i, j, k, max: Integer;
    s: String;
    last: Array [1..150] of Integer;
    f: TEXT;
begin
    Assign(f, '24-263.txt');
    Reset(f);
    Readln(f, s);
    k := 0;
    max := 0;
    for i := 1 to 150 do
        last[i] := 0;
    for i := 1 to s.Length do
        if s[i] = 'Y' then
        begin
            if last[1] = 0 then
            begin
                k := k + 1;
                if k > max then
                    max := k;
            end
            else
                k := i - last[1];
            for j := 1 to 149 do
                last[j] := last[j + 1];
            last[150] := i;
        end
        else
        begin
            k := k + 1;
            if k > max then
                max := k;
        end;
    Writeln(max);
end.

PascalABC с использованием динамического массива

var
    i, k, max: Integer;
    s: String;
    last: Array of Integer := ArrFill(150, 0);
    f: TEXT;
begin
    Assign(f, '24-263.txt');
    Reset(f);
    Readln(f, s);
    k := 0;
    max := 0;
    for i := 1 to s.Length do
        if s[i] = 'Y' then
        begin
            if last[0] = 0 then
            begin
                k := k + 1;
                if k > max then
                    max := k;
            end
            else
                k := i - last[0];
            last := last[1:] + Arr(i);
        end
        else
        begin
            k := k + 1;
            if k > max then
                max := k;
        end;
    Writeln(max);
end.

C++ с использованием статического массива

#include <iostream>
#include <fstream>
using namespace std;
int main()
{
    ifstream f;
    f.open("24-263.txt");
    string s;
    f >> s;
    int k = 0, max = 0;
    int last[150];
    for (int i = 0; i < 150; i++)
        last[i] = -1;
    for (int i = 0; i < s.length(); i++)
        if (s[i] == 'Y')
        {
            if (last[0] == -1)
            {
                k++;
                if (k > max)
                    max = k;
            }
            else
                k = i - last[0];
            for (int i = 0; i < 149; i++)
                last[i] = last[i + 1];
            last[149] = i;
        }
        else
        {
            k++;
            if (k > max)
                max = k;
        }
    cout << max << endl;
}

C++ с использованием vector

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int main()
{
    ifstream f;
    f.open("24-263.txt");
    string s;
    f >> s;
    int k = 0, max = 0;
    vector<int> last;
    for (int i = 0; i < 150; i++)
        last.push_back(-1);
    for (int i = 0; i < s.length(); i++)
        if (s[i] == 'Y')
        {
            if (last[0] == -1)
            {
                k++;
                if (k > max)
                    max = k;
            }
            else
                k = i - last[0];
            last.erase(last.begin());
            last.push_back(i);
        }
        else
        {
            k++;
            if (k > max)
                max = k;
        }
    cout << max << endl;
}

Ответ

5195

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