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

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

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

Например, для числа 13 = 1101₂ получается 111101₂ = 61, для числа 10 = 1010₂ получается 1101010₂ = 106. Укажите максимальное число R, не превышающее 223, которое может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.

Решение

Еще одна задача, где на Python решение через эквивалентные целочисленные операции близко по объему кода к решению через строки. На PascalABC и C++ такое решение всегда предпочтительнее.

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

mx = 0
for n in range(1, 100):
    s = bin(n)[2:]
    if n % 5 == 0:
        s = '1' + s + s[-2:]
    else:
        s = bin(n % 5)[2:] + s
    r = int(s, 2)
    if r <= 223:
        mx = max(mx, r)
print(mx)

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

mx = 0
for n in range(1, 100):
    z = 1
    while z <= n:
        z *= 2
    if n % 5 == 0:
        r = (z + n) * 4 + n % 4
    else:
        r = n % 5 * z + n
    if r <= 223:
        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 := 1 to 99 do
    begin
        s := Bin(n);
        if n mod 5 = 0 then
            s := '1' + s + s[s.Length - 1:]
        else
            s := Bin(n mod 5) + s;
        r := Int(s, 2);
        if (r <= 223) and (r > max) then
            max := r;
    end;
    Writeln(max);
end.

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

var
    n, max, r, z: Integer;
begin
    max := 0;
    for n := 1 to 99 do
    begin
        z := 1;
        while z <= n do
            z := z * 2;
        if n mod 5 = 0 then
          r := (z + n) * 4 + n mod 4
        else
            r := n mod 5 * z + n;
        if (r <= 223) 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 = 1; n < 100; n++)
    {
        string s = bin(n);
        if (n % 5 == 0)
            s = "1" + s + s.substr(s.length() - 2, 2);
        else
            s = bin(n %  5) + s;
        int r = to_int(s, 2);
        if (r <= 223 && 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++)
    {
        int z = 1;
        while (z <= n)
            z *= 2;
        if (n % 5 == 0)
            r = (z + n) * 4 + n % 4;
        else
            r = n % 5 * z + n;
        if (r <= 223 && r > max)
            max = r;
    }
    cout << max << endl;
}

Ответ

219