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

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

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

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

Например, для исходного числа 12₁₀ = 1100₂ результатом является число 1100100₂ = 100₁₀, а для исходного числа 4₁₀ = 100₂ результатом является число 10011₂ = 19₁₀.

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

Решение

Будем перебирать значения n от 4 (минимальное число, которое имеет ри двоичных разряда) до заведомо достаточного конечного значения и анализировать результат алгоритма. Сам алгоритм можно реализовать через эквивалентные целочисленные операции или через строки. Самые продвинутые вместо операции умножения могут использовать операцию сдвига на нужное количество двоичных разрядов.

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

for n in range(4, 100):
    if n % 3 == 0:
        r = n * 8 + n % 8
    else:
        z = n % 3 * 3
        m = 2
        while m <= z:
            m *= 2
        r = n * m + z
    if r >= 120:
        print(n)
        break

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

for n in range(4, 100):
    s = bin(n)[2:]
    if n % 3 == 0:
        s += s[-3:]
    else:
        s += bin(n % 3 * 3)[2:]
    r = int(s, 2)
    if r >= 120:
        print(n)
        break

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

var
    n, r, z, m: Integer;
begin
    for n := 4 to 99 do
    begin
        if n mod 3 = 0 then
            r := n * 8 + n mod 8
        else
        begin
            z := n mod 3 * 3;
            m := 2;
            while m <= z do
                m := m * 2;
            r := n * m + z;
        end;
        if r >= 120 then
        begin
            Writeln(n);
            break;
        end;
    end;
end.

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

function Bin(n: Integer): String;
begin
    result := '';
    while n > 0 do
    begin
        result := IntToStr((n mod 2)) + result;
        n := n div 2;
    end;
    if result = '' then
        result := '0';
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: Integer;
    s: String;
begin
    for n := 4 to 99 do
    begin
        s := Bin(n);
        if n mod 3 = 0 then
            s := s + s[s.Length - 2:]
        else
            s := s + Bin(n mod 3 * 3);
        r := Int(s, 2);
        if r >= 120 then
        begin
            Writeln(n);
            break;
        end;
    end;
end.

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

#include <iostream>
using namespace std;
int main()
{
    for (int n = 4; n < 100; n++)
    {
        int r;
        if (n % 3 == 0)
            r = n * 8 + n % 8;
        else
        {
            int z = n % 3 * 3;
            int m = 2;
            while (m <= z)
                m *= 2;
            r = n * m + z;
        }
        if (r >= 120)
        {
            cout << n << endl;
            break;
        }
    }
}

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

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

string bin(int n)
{
    string s = "";
    while (n > 0)
    {
        s = to_string(n % 2) + s;
        n /= 2;
    }
    if (s == "")
        s = "0";
    return s;
}

int to_int(string s, int r)
{
    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()
{
    for (int n = 4; n < 100; n++)
    {
        string s = bin(n);
        if (n % 3 == 0)
            s += s.substr(s.length() - 3, 3);
        else
            s += bin(n % 3 * 3);
        int r = to_int(s, 2);
        if (r >= 120)
        {
            cout << n << endl;
            break;
        }
    }
}