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

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

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

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

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

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

НАЧАЛО
ПОКА нашлось (18) ИЛИ нашлось (388) ИЛИ нашлось (888)
  ЕСЛИ нашлось (18)
    ТО заменить (18, 8)
  КОНЕЦ ЕСЛИ
  ЕСЛИ нашлось (388)
    ТО заменить (388, 81)
  КОНЕЦ ЕСЛИ
  ЕСЛИ нашлось (888)
    ТО заменить (888, 3)
  КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

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

Решение

Реализуем алгоритм на выбранном языке программирования и в цикле найдем значение n, удовлетворяющее условию.

Python

for n in range(4, 10000):
    s = '1' + '8' * n
    while '18' in s or '388' in s or '888' in s:
        if '18' in s:
            s = s.replace('18', '8', 1)
        if '388' in s:
            s = s.replace('388', '81', 1)
        if '888' in s:
            s = s.replace('888', '3', 1)
    if s.count("1") == 3:
        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;

function count(s: String; c: Char): Integer;
var
    i: Integer;
begin
    result := 0;
    for i := 1 to s.Length do
        if s[i] = c then
            result := result + 1;
end;

var
    n: Integer;
    s: String;
begin
    for n := 4 to 9999 do
    begin
        s := '1' + '8' * n;
        while s.Contains('18') or s.Contains('388') or s.Contains('888') do
        begin
            if s.Contains('18') then
                s := replace(s, '18', '8');
            if s.Contains('388') then
                s := replace(s, '388', '81');
            if s.Contains('888') then
                s := replace(s, '888', '3');
        end;
        if count(s, '1') = 3 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 count(string s, char c)
{
    int k = 0;
    for (int i = 0; i < s.length(); i++)
        if (s[i] == c)
            k++;
    return k;
}

int main()
{
    for (int n = 4; n < 10000; n++)
    {
        string s = "1" + mul("8", n);
        while (s.find("18") != -1 || s.find("388") != -1 || s.find("888") != -1)
        {
            if (s.find("18") != -1)
                s = replace(s, "18", "8");
            if (s.find("388") != -1)
                s = replace(s, "388", "81");
            if (s.find("888") != -1)
                s = replace(s, "888", "3");
        }
        if (count(s, '1') == 3)
        {
            cout << n << endl;
            break;
        }
    }
}

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

Решение

Python

PascalABC

C++

Ответ

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