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

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

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

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

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

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

НАЧАЛО
ПОКА нашлось (72) ИЛИ нашлось (522) ИЛИ нашлось (2222)
  ЕСЛИ нашлось (72)
    ТО заменить (72, 2)
  КОНЕЦ ЕСЛИ
  ЕСЛИ нашлось (522)
    ТО заменить (522, 27)
  КОНЕЦ ЕСЛИ
  ЕСЛИ нашлось (2222)
    ТО заменить (2222, 5)
  КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

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

Решение

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

Python

for n in range(4, 10000):
    s = '5' + '2' * n
    while '72' in s or '522' in s or '2222' in s:
        if '72' in s:
            s = s.replace('72', '2', 1)
        if '522' in s:
            s = s.replace('522', '27', 1)
        if '2222' in s:
            s = s.replace('2222', '5', 1)
    sm = 0
    for i in s:
        sm += int(i)
    if sm == 63:
        print(n)
        break

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, sum, i: Integer;
    s: String;
begin
    for n := 4 to 9999 do
    begin
        s := '5' + '2' * n;
        while s.Contains('72') or s.Contains('522') or s.Contains('2222') do
        begin
            if s.Contains('72') then
                s := replace(s, '72', '2');
            if s.Contains('522') then
                s := replace(s, '522', '27');
            if s.Contains('2222') then
                s := replace(s, '2222', '5');
        end;
        sum := 0;
        for i := 1 to s.Length do
            sum := sum + StrToInt(s[i]);
        if sum = 63 then
        begin
            Writeln(n);
            break;
        end;
    end;
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()
{
    for (int n = 4; n < 10000; n++)
    {
        string s = "5" + mul("2", n);
        while (s.find("72") != -1 || s.find("522") != -1 || s.find("2222") != -1)
        {
            if (s.find("72") != -1)
                s = replace(s, "72", "2");
            if (s.find("522") != -1)
                s = replace(s, "522", "27");
            if (s.find("2222") != -1)
                s = replace(s, "2222", "5");
        }
        int sum = 0;
        for (int i = 0; i < s.length(); i++)
            sum += (int)s[i] - 48;
        if (sum == 63)
        {
            cout << n << endl;
            break;
        }
    }
}

Ответ

186

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

Решение

Python

PascalABC

C++

Ответ

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