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

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

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

Из числа N вычитается количество нулей в двоичной записи числа N.
Строится двоичная запись полученного числа.
К полученной записи слева дописывается три младших разряда.
Результат переводится в десятичную систему и выводится на экран.

Пример. Дано число N = 13. Алгоритм работает следующим образом:

Двоичная запись числа 13 = 1101₂ содержит один 0. 13 – 1 = 12.
12₁₀ = 1100₂
1100 -> 1001100
1001100₂ = 76

Какое наименьшее число, большее 224, может появиться на экране в результате работы автомата?

Решение

Как обычно, решим задачу через строки и операции с целыми числами.

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

mn = 10000
for n in range(5, 100):
    s = bin(n)[2:]
    s = bin(n - s.count('0'))[2:]
    s = s[-3:] + s
    r = int(s, 2)
    if r > 224:
        mn = min(mn, r)
print(mn)

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

mn = 10000
for n in range(5, 100):
    z = n
    r = n
    while z > 0:
        if z % 2 == 0:
            r -= 1
        z //= 2
    z = 1
    while z <= r:
        z *= 2
    r += r % 8 * z
    if r > 224:
        mn = min(mn, r)
print(mn)

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;
function Count(s: String; c: Char): Integer;
var
    i: Integer;
begin
    result := 0;
    for i := 1 to s.Length do
        if s[i] = c then
            result := result + 1;
end;
var
    n, r, min: Integer;
    s: String;
begin
    min := 10000;
    for n := 5 to 99 do
    begin
        s := Bin(n);
        s := Bin(n - Count(s, '0'));
        s := s[s.Length - 2:] + s;
        r := Int(s, 2);
        if (r > 224) and (r < min) then
            min := r;
    end;
    Writeln(min);
end.

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

var
    n, r, z, min: Integer;
begin
    min := 10000;
    for n := 5 to 99 do
    begin
        z := n;
        r := n;
        while z > 0 do
        begin
            if z mod 2 = 0 then
                r := r - 1;
            z := z div 2;
        end;
        z := 1;
        while z <= r do
            z := z * 2;
        r := r + r mod 8 * z;
        if (r > 224) and (r < min) then
            min := r;
    end;
    Writeln(min);
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 count(string s, char c)
{
    int n = 0;
    for (int i = 0; i < s.length(); i++)
        if (s[i] == c)
            n++;
    return n;
}
int main()
{
    int min = 10000;
    for (int n = 5; n < 100; n++)
    {
        string s = bin(n);
        s = bin(n - count(s, '0'));
        s = s.substr(s.length() - 3, 3) + s;
        int r = to_int(s, 2);
        if (r > 224 && r < min)
            min = r;
    }
    cout << min << endl;
}

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

#include <iostream>
using namespace std;
int main()
{
    int min = 10000;
    for (int n = 5; n < 100; n++)
    {
        int z = n, r = n;
        while (z > 0)
        {
            if (z % 2 == 0)
                r--;
            z /= 2;
        }
        z = 1;
        while (z <= r)
            z *= 2;
        r += r % 8 * z;
        if (r > 224 && r < min)
            min = r;
    }
    cout << min << endl;
}

Ответ

227