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

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

Строится двоичная запись числа N.
К этой записи дописываются еще несколько разрядов по следующему правилу:

если N четное, то к нему справа приписываются два нуля, а слева единица;
если N нечетное, то к нему справа приписывается в двоичном виде сумма цифр его двоичной записи;

Полученная таким образом запись (в ней как минимум на один разряд больше, чем в записи исходного числа N) является двоичной записью искомого числа R.

Полученная таким образом запись является двоичной записью искомого числа R. Например, исходное число 4₁₀ = 100₂ преобразуется число 11000₂ = 48₁₀, а исходное число 13₁₀ = 1101₂ преобразуется в число 110111₂ = 55₁₀. Укажите такое число N большее 8, для которого число R является наименьшим среди чисел, превышающих 88. В ответе это число запишите в десятичной системе счисления.

Решение

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

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

mn = 1000
mnn = 0
for n in range(9, 100):
    s = bin(n)[2:]
    if s[-1] == '0':
        s = '1' + s + '00'
    else:
        s += bin(s.count('1'))[2:]
    r = int(s, 2)
    if r > 88 and r < mn:
        mn = r
        mnn = n
print(mnn)

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

mn = 1000
mnn = 0
for n in range(9, 100):
    if n % 2 == 0:
        z = n
        k = 0
        while z > 0:
            k += 1
            z //= 2
        r = (2 ** k + n) * 4
    else:
        z = n
        sm = 0
        while z > 0:
            sm += z % 2
            z //= 2
        z = 2
        while z <= sm:
            z *= 2
        r = n * z + sm
    if r > 88 and r < mn:
        mn = r
        mnn = n
print(mnn)

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, minn: Integer;
    s: String;
begin
    min := 1000;
    minn := 0;
    for n := 9 to 99 do
    begin
        s := Bin(n);
        if s[s.Length] = '0' then
            s := '1' + s + '00'
        else
            s := s + Bin(Count(s, '1'));
        r := Int(s, 2);
        if (r > 88) and (r < min) then
        begin
            min := r;
            minn := n;
        end;
    end;
    Writeln(minn);
end.

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

var
    n, r, z, k, sum, min, minn: Integer;
begin
    min := 1000;
    minn := 0;
    for n := 9 to 99 do
    begin
        if n mod 2 = 0 then
        begin
            z := n;
            k := 0;
            while z > 0 do
            begin
                k := k + 1;
                z := z div 2;
            end;
            r := (round(power(2, k)) + n) * 4;
        end
        else
        begin
            z := n;
            sum := 0;
            while z > 0 do
            begin
                sum := sum + z mod 2;
                z := z div 2;
            end;
            z := 2;
            while z <= sum do
                z := z * 2;
            r := n * z + sum;
        end;
        if (r > 88) and (r < min) then
        begin
            min := r;
            minn := n;
        end;
    end;
    Writeln(minn);
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 = 1000, minn = 0;
    for (int n = 9; n < 100; n++)
    {
        string s = bin(n);
        if (s[s.length() - 1] == '0')
            s = "1" + s + "00";
        else
            s += bin(count(s, '1'));
        int r = to_int(s, 2);
        if (r > 88 && r < min)
        {
            min = r;
            minn = n;
        }
    }
    cout << minn << endl;
}

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

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    int min = 1000, minn = 0;
    for (int n = 9; n < 100; n++)
    {
        int r;
        if (n % 2 == 0)
        {
            int z = n, k = 0;
            while (z > 0)
            {
                k++;
                z /= 2;
            }
            r = ((int)pow(2, k) + n) * 4;
        }
        else
        {
            int z = n, sum = 0;
            while (z > 0)
            {
                sum += z % 2;
                z /= 2;
            }
            z = 2;
            while (z <= sum)
                z *= 2;
            r = n * z + sum;
        }
        if (r > 88 && r < min)
        {
            min = r;
            minn = n;
        }
    }
    cout << minn << endl;
}