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

(ЕГЭ-2023) На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом:

Строится троичная запись числа N.
Если число N делится на 3, к троичной записи справа дописываются две её последние цифры, иначе остаток от деления числа на 3 умножается на 5, переводится в троичную систему и дописывается в конец троичной записи.
Полученная таким образом запись является троичной записью искомого числа R.

Например, для числа 11 троичная запись 102₃ преобразуется в запись 102101₃ = 307, для числа 12 троичная запись 110₃ преобразуется в 11010₃ = 111. Укажите минимальное значение R, большее чем 133, которое может быть результатом работы алгоритма.

Решение

Как и большинство других задач, решение возможно через работу со строками или через эквивалентные целочисленные операции. Решение через целочисленные операции даже на Python потребует написание меньшего объема кода, т.к. для решения через строки необходимо написать функцию перевода десятичного числа в строку с троичным представлением. Для перебора вполне достаточен диапазон от 3 (минимальное двузначное число в троичной системе) до 29 (при обработке алгоритмом число увеличивается на 2 или 3 троичных разряда, т.е. в 9 или 27 раз).

Python через строки

def ter(n):
    t = ''
    while n > 0:
        t = str(n % 3) + t
        n //= 3
    return t


mn = 10000
for n in range(3, 30):
    s = ter(n)
    if n % 3 == 0:
        s += s[-2:]
    else:
        s += ter(n % 3 * 5)
    r = int(s, 3)
    if r > 133:
        mn = min(mn, r)
print(mn)

Python через целочисленные операции

mn = 10000
for n in range(3, 30):
    if n % 3 == 0:
        r = n * 9 + n % 9
    elif n % 3 == 1:
        r = n * 9 + 5
    else:
        r = n * 27 + 10
    if r > 133:
        mn = min(mn, r)
print(mn)

PascalABC через строки

function Ter(n: Integer): String;
begin
    result := '';
    while n > 0 do
    begin
        result := IntToStr(n mod 3) + result;
        n := n div 3;
    end;
end;

function Int(s: String; r: Integer := 10): Integer;
var
    n, i: Integer;
begin
    result := 0;
    n := 1;
    for i := s.Length downto 1 do
    begin
        result := result + StrToInt(s[i]) * n;
        n := n * r;
    end;
end;

var
    n, r, min: Integer;
    s: String;
begin
    min := 10000;
    for n := 3 to 29 do
    begin
        s := Ter(n);
        if n mod 3 = 0 then
            s := s + s[s.Length -1:]
        else
        begin
            s := s + Ter(n mod 3 * 5);
        end;
        r := Int(s, 3);
        if (r > 133) and (r < min) then
            min := r;
    end;
    Writeln(min);
end.

PascalABC через целочисленные операции

var
    n, min, r: Integer;
begin
    min := 10000;
    for n := 3 to 29 do
    begin
        if n mod 3 = 0 then
            r := n * 9 + n mod 9
        else if n mod 3 = 1 then
            r := n * 9 + 5
        else
            r := n * 27 + 10;
        if (r > 133) and (r < min) then
            min := r;
    end;
    Writeln(min);
end.

C++ через строки

#include <iostream>
#include <string>
using namespace std;
string ter(int n)
{
    string t = "";
    while (n > 0)
    {
        t = to_string(n % 3) + t;
        n /= 3;
    }
    return t;
}
int to_int(string s, int r = 10)
{
    int n = 0, z = 1;
    for (int i = s.length() - 1; i >= 0; i--)
    {
        n += ((int)s[i] - 48) * z;
        z *= r;
    }
    return n;
}
int main()
{
    int min = 10000;
    for (int n = 3; n < 30; n++)
    {
        string s = ter(n);
        if (n % 3 == 0)
            s += s.substr(s.length() - 2, 2);
        else
            s += ter(n % 3 * 5);
        int r = to_int(s, 3);
        if (r > 133 && r < min)
            min = r;
    }
    cout << min << endl;
}

C++ через целочисленные операции

#include <iostream>
using namespace std;
int main()
{
    int min = 10000, r;
    for (int n = 3; n < 30; n++)
    {
        if (n % 3 == 0)
            r = n * 9 + n % 9;
        else if (n % 3 == 0)
            r = n * 9 + 5;
        else
            r = n * 27 + 10;
        if (r > 133 && r < min)
            min = r;
    }
    cout << min << endl;
}

Ответ

141