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

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

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

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

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

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

НАЧАЛО
ПОКА нашлось(555) ИЛИ нашлось(11) ИЛИ нашлось(2)
  ЕСЛИ нашлось(555)
    ТО заменить(555,1)
  КОНЕЦ ЕСЛИ
  ЕСЛИ нашлось(11)
    ТО заменить(11,25)
  КОНЕЦ ЕСЛИ
  ЕСЛИ нашлось(2)
    ТО заменить(2, 5)
  КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

На вход приведённой выше программе поступает строка, содержащая n цифр 5. Определите наименьшее значение n, большее 100, при котором в результате работы алгоритма получится строка 15.

Решение

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

Python

for n in range(101, 1000):
    s = '5' * n
    while '555' in s or '11' in s or '2' in s:
        if '555' in s:
            s = s.replace('555', '1', 1)
        if '11' in s:
            s = s.replace('11', '25', 1)
        if '2' in s:
            s = s.replace('2', '5', 1)
    if s == '15':
        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: Integer;
    s: String;
begin
    for n := 101 to 999 do
    begin
        s := '5' * n;
        while s.Contains('555') or s.Contains('11') or s.Contains('2') do
        begin
            if s.Contains('555') then
                s := replace(s, '555', '1');
            if s.Contains('11') then
                s := replace(s, '11', '25');
            if s.Contains('2') then
                s := replace(s, '2', '5');
        end;
        if s = '15' 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 = 101; n < 1000; n++)
    {
        string s = mul("5", n);
        while (s.find("555") != -1 || s.find("11") != -1 || s.find("2") != -1)
        {
            if (s.find("555") != -1)
                s = replace(s, "555", "1");
            if (s.find("11") != -1)
                s = replace(s, "11", "25");
            if (s.find("2") != -1)
                s = replace(s, "2", "5");
        }
        if (s == "15")
        {
            cout << n << endl;
            break;
        }
    }
}

Ответ

104

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

Решение

Python

PascalABC

C++

Ответ

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