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

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

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

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

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

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

НАЧАЛО
ПОКА НЕ нашлось (00)
  заменить (02, 101)
  заменить (11, 2)
  заменить (012, 30)
  заменить (010, 00)
КОНЕЦ ПОКА
КОНЕЦ

Известно, что исходная строка содержала ровно два нуля – на первом и на последнем месте, 100 единиц, больше 50 двоек и не содержала других цифр. После выполнения программы получилась строка, сумма цифр которой оказалась простым числом. Какое наименьшее количество двоек могло быть в исходной строке?

Решение

По всей видимости, разработчики рассчитывали, что два нуля в строке могут быть получены только за счет четвертой замены, которая уменьшает сумму в строке на единицу (первые три замены сумму в строке не меняют). Однако, для некоторых строк два нуля может дать и третья замена. Решением данной задачи является перебор различных вариантов расположения двоек и единиц для различных значений n, пока не получим сумму, являющуюся простым числом.

Python

def simple(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True


def algo(s):
    while '00' not in s:
        s = s.replace('02', '101', 1)
        s = s.replace('11', '2', 1)
        s = s.replace('012', '30', 1)
        s = s.replace('010', '00', 1)
    sm = 0
    for i in s:
        sm += int(i)
    return sm


for n in range(51, 101):
    variants = ['0' + '2' * n + '1' * 100 + '0',
                '0' + '1' * 100 + '2' * n + '0',
                '0' + '12' * n + '1' * (100 - n) + '0',
                '0' + '21' * n + '1' * (100 - n) + '0',
                '0' + '1' * (100 - n) + '12' * n + '0',
                '0' + '1' * (100 - n) + '21' * n + '0']
    for s in variants:
        if simple(algo(s)):
            print(n)
            exit()

PascalABC

function simple(n: Integer): Boolean;
var
    i: Integer;
begin
    Result := True;
    for i := 2 to round(sqrt(n)) do
        if n mod i = 0 then
        begin
            Result := False;
            break;
        end;
end;

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 algo(s: String): Integer;
var
    i: Integer;
begin
    while not s.Contains('00') do
    begin
        s := replace(s, '02', '101');
        s := replace(s, '11', '2');
        s := replace(s, '012', '30');
        s := replace(s, '010', '00');
    end;
    result := 0;
    for i := 1 to s.Length do
        result := result + StrToInt(s[i]);
end;

var
    n: Integer;
    variants: Set of String;
    s: String;
begin
    for n := 51 to 100 do
    begin
        variants := ['0' + '2' * n + '1' * 100 + '0',
                     '0' + '1' * 100 + '2' * n + '0',
                     '0' + '12' * n + '1' * (100 - n) + '0',
                     '0' + '21' * n + '1' * (100 - n) + '0',
                     '0' + '1' * (100 - n) + '12' * n + '0',
                     '0' + '1' * (100 - n) + '21' * n + '0'];
        foreach s in variants do
            if simple(algo(s)) then
            begin
               Writeln(n);
               Exit;
            end;
    end;
end.

C++

#include <iostream>
#include <string>
using namespace std;

bool simple(int n)
{
    for (int i = 2; i <= sqrt(n); i++)
        if (n % i == 0)
            return false;
    return true;
}

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 algo(string s)
{
    while (s.find("00") == -1)
    {
        s = replace(s, "02", "101");
        s = replace(s, "11", "2");
        s = replace(s, "012", "30");
        s = replace(s, "010", "00");
    }
    int sum = 0;
    for (int i = 0; i < s.length(); i++)
        sum += (int)s[i] - 48;
    return sum;
}

int main()
{
    for (int n = 51; n < 101; n++)
    {
        string variants[6] = { "0" + mul("2", n) + mul("1", 100) + "0",
                                "0" + mul("1", 100) + mul("2", n) + "0",
                                "0" + mul("12", n) + mul("1", 100 - n) + "0",
                                "0" + mul("21", n) + mul("1", 100 - n) + "0",
                                "0" + mul("1", 100 - n) + mul("12", n) + "0",
                                "0" + mul("1", 100 - n) + mul("21", n) + "0" };
        for (int i = 0; i < 6; i++)
            if (simple(algo(variants[i])))
            {
                cout << n << endl;
                return 0;
            }
    }
}

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

Решение

Python

PascalABC

C++

Ответ

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