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

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

(ЕГЭ-2023) Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки символов.

заменить (v, w)
2. нашлось (v)

Первая команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Если цепочки v в строке нет, эта команда не изменяет строку. Вторая команда проверяет, встречается ли цепочка v в строке исполнителя Редактор.

Дана программа для исполнителя Редактор:

НАЧАЛО
ПОКА нашлось (12) ИЛИ нашлось (322) ИЛИ нашлось (222)
  ЕСЛИ нашлось (12)
    ТО заменить (12, 2)
  КОНЕЦ ЕСЛИ
  ЕСЛИ нашлось (322)
    ТО заменить (322, 21)
  КОНЕЦ ЕСЛИ
  ЕСЛИ нашлось (222)
    ТО заменить (222, 3)
  КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

На вход приведённой выше программе поступает строка, начинающаяся с цифры «1», а затем содержащая n цифр «2» (3 < n < 10 000). Определите наибольшее возможное значение суммы числовых значений цифр в строке, которая может быть результатом выполнения программы.

Решение

Перебираем значения n в указанном диапазоне, формируем строку, обрабатываем ее алгоритмом, находим сумму цифр и анализируем полученный результат.

Python

mx = 0
for n in range(4, 10000):
    s = '1' + '2' * n
    while '12' in s or '322' in s or '222' in s:
        if '12' in s:
            s = s.replace('12', '2', 1)
        if '322' in s:
            s = s.replace('322', '21', 1)
        if '222' in s:
            s = s.replace('222', '3', 1)
    sm = 0
    for i in s:
        sm += int(i)
    mx = max(mx, sm)
print(mx)

PascalABC

function replace(s, s1, s2: String): String;
var
    p: Integer;
begin
    result := s;
    if s.Contains(s1) then
    begin
        p := s.IndexOf(s1) + 1;
        result := s[:p] + s2 + ((p + s1.Length <= s.Length) ? s[p + s1.Length:] : '');
    end
end;

var
    n, max, sum, i: Integer;
    s: String;
begin
    max := 0;
    for n := 4 to 9999 do
    begin
        s := '1' + '2' * n;
        while s.Contains('12') or s.Contains('322') or s.Contains('222') do
        begin
            if s.Contains('12') then
                s := replace(s, '12', '2');
            if s.Contains('322') then
                s := replace(s, '322', '21');
            if s.Contains('222') then
                s := replace(s, '222', '3');
        end;
        sum := 0;
        for i := 1 to s.Length do
            sum := sum + StrToInt(s[i]);
        if sum > max then
            max := sum;
    end;
    Writeln(max);
end.

C++

#include <iostream>
using namespace std;

string replace(string s, string s1, string s2)
{
    int p = s.find(s1);
    if (p != -1)
        return s.substr(0, p) + s2 + s.substr(p + s1.length(), s.length() - p - s1.length());
    return s;
}

string mul(string s, int n)
{
    string res = "";
    for (int i = 0; i < n; i++)
        res += s;
    return res;
}

int main()
{
    int max = 0;
    for (int n = 4; n < 10000; n++)
    {
        string s = "1" + mul("2", n);
        while (s.find("12") != -1 || s.find("322") != -1 || s.find("222") != -1)
        {
            if (s.find("12") != -1)
                s = replace(s, "12", "2");
            if (s.find("322") != -1)
                s = replace(s, "322", "21");
            if (s.find("222") != -1)
                s = replace(s, "222", "3");
        }
        int sum = 0;
        for (int i = 0; i < s.length(); i++)
            sum += (int)s[i] - 48;
        if (sum > max)
            max = sum;
    }
    cout << max << endl;
}

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

Решение

Python

PascalABC

C++

Ответ

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