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

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

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

Например, для числа 11 троичная запись 102₃ преобразуется в запись 10222₃ = 107, для числа 12 троичная запись 110₃ преобразуется в 111002₃ = 353. Укажите максимальное значение N, после обработки которого с помощью этого алгоритма получается число R, меньшее чем 199.

Решение

Задачи с дописыванием разрядов слева помимо решения через строки так же можно решать через эквивалентные целочисленные операции. В данном случае, даже на Python такое решение требует написания меньшего объема кода, чем решение на основе работы со строками.

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

mx = 0
for n in range(1, 30):
    if n % 3 == 0:
        r = n * 9 + 2
        z = 1
        while z <= r:
            z *= 3
        r += z
    elif n % 3 == 1:
        r = n * 9 + 4
    else:
        r = n * 9 + 8
    if r < 199:
        mx = n
print(mx)

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

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


mx = 0
for n in range(1, 30):
    s = ter(n)
    if n % 3 == 0:
        s = '1' + s + '02'
    else:
        s += ter(n % 3 * 4)
    r = int(s, 3)
    if r < 199:
        mx = n
print(mx)

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

var
    n, max, r, z: Integer;
begin
    max := 0;
    for n := 1 to 29 do
    begin
        if n mod 3 = 0 then
        begin
            r := n * 9 + 2;
            z := 1;
            while z <= r do
                z := z * 3;
            r := r + z;
        end
        else if n mod 3 = 1 then
            r := n * 9 + 4
        else
            r := n * 9 + 8;
        if r <199 then
            max := n;
    end;
    Writeln(max);
end.

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, max: Integer;
    s: String;
begin
    max := 0;
    for n := 1 to 29 do
    begin
        s := Ter(n);
        if n mod 3 = 0 then
            s := '1' + s + '02'
        else
        begin
            s := s + Ter(n mod 3 * 4);
        end;
        r := Int(s, 3);
        if r <199 then
            max := n;
    end;
    Writeln(max);
end.

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

#include <iostream>
using namespace std;
int main()
{
    int max = 0, r;
    for (int n = 1; n < 30; n++)
    {
        if (n % 3 == 0)
        {
            r = n * 9 + 2;
            int z = 1;
            while (z <= r)
                z *= 3;
            r += z;
        }
        else if (n % 3 == 0)
            r = n * 9 + 4;
        else
            r = n * 9 + 8;
        if (r < 199)
            max = n;
    }
    cout << max << endl;
}

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 max = 0;
    for (int n = 1; n < 30; n++)
    {
        string s = ter(n);
        if (n % 3 == 0)
            s = "1" + s + "02";
        else
            s += ter(n % 3 * 4);
        int r = to_int(s, 3);
        if (r < 199)
            max = n;
    }
    cout << max << endl;
}