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

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

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

Например, для числа 12 двоичная запись 1100₂ преобразуется в запись 1100100₂ = 100, для числа 4 двоичная запись 100₂ преобразуется в 10011₂ = 19. Укажите максимальное возможное значение R, меньшее 170, которое может быть получено с помощью этого алгоритма. В ответе запишите это число в десятичной системе счисления.

Решение

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

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

mx = 0
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 < 170:
        mx = max(mx, r)
print(mx)

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

mx = 0
for n in range(4, 100):
    if n % 3 == 0:
        r = n * 8 + n % 8
    elif n % 3 == 1:
        r = n * 4 + 3
    else:
        r = n * 8 + 6
    if r < 170:
        mx = max(mx, r)
print(mx)

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, max, r: Integer;
    s: String;
begin
    max := 0;
    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 < 170) and (r > max) then
            max := r;
    end;
    Writeln(max);
end.

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

var
    n, max, r: Integer;
begin
    max := 0;
    for n := 4 to 99 do
    begin
        if n mod 3 = 0 then
          r := n * 8 + n mod 8
        else if n mod 3 = 1 then
            r := n * 4 + 3
        else
            r := n * 8 + 6;
        if (r < 170) and (r > max) then
            max := r;
    end;
    Writeln(max);
end.

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

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

#include <iostream>
using namespace std;
int main()
{
    int max = 0, r;
    for (int n = 1; n < 100; n++)
    {
        if (n % 3 == 0)
            r = n * 8 + n % 8;
        else if (n % 3 == 0)
            r = n * 4 + 3;
        else
            r = n * 8 + 6;
        if (r < 170 && r > max)
            max = r;
    }
    cout << max << endl;
}

Ответ

166