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

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

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

Строится троичная запись числа N.
Далее эта запись обрабатывается по следующему правилу:
1. если число N чётное, в конец дописываются два младших разряда полученной троичной записи;
2. если число N нечётное, в конец дописывается троичное представление суммы цифр полученной троичной записи.
Полученная таким образом запись является троичной записью искомого числа R.

Например, для исходного числа 10₁₀ = 101₃ результатом является число 10101₃ = 91₁₀, а для исходного числа 11₁₀ = 102₃ результатом является число 10210₃ = 102₁₀.

Укажите значение N, после обработки которого с помощью этого алгоритма получается минимальное число R. В ответе запишите это число в десятичной системе счисления.

Решение

Создадим функцию преобразования числа в строковое троичное представление ter(n) и, перебрав некоторый диапазон n, найдем ответ на задачу.

Python

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


mn = 10000
mnn = 0
for n in range(10, 1000):
    s = ter(n)
    if n % 2 == 0:
        s += s[-2:]
    else:
        s += ter(sum([int(x) for x in s]))
    r = int(s, 3)
    if r < mn:
        mn = r
        mnn = n
print(mnn)

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, minn, sum, i: Integer;
    s: String;
begin
    min := 10000;
    minn := 0;
    for n := 10 to 999 do
    begin
        s := Ter(n);
        if n mod 2 = 0 then
            s := s + s[s.Length -1:]
        else
        begin
            sum := 0;
            for i := 1 to s.Length do
                sum:= sum + StrToInt(s[i]);
            s := s + Ter(sum);
        end;
        r := Int(s, 3);
        if r < min then
        begin
            min := r;
            minn := n;
        end;
    end;
    Writeln(minn);
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, minn = 0;
    for (int n = 10; n < 1000; n++)
    {
        string s = ter(n);
        if (n % 2 == 0)
            s += s.substr(s.length() - 2, 2);
        else
        {
            int sum = 0;
            for (int i = 0; i < s.length(); i++)
                sum += (int)s[i] - 48;
            s += ter(sum);
        }
        int r = to_int(s, 3);
        if (r < min)
        {
            min = r;
            minn = n;
        }
    }
    cout << minn << endl;
}

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

Решение

Python

PascalABC

C++

Ответ

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