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

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

Строится двоичная запись числа N.
Далее эта запись обрабатывается по следующему правилу:
1. если сумма цифр в двоичной записи числа чётная, то к этой записи справа дописывается 00, а затем два левых разряда заменяются на 11;
2. если сумма цифр в двоичной записи числа нечётная, то к этой записи справа дописывается 11, а затем два левых разряда заменяются на 10.
Для полученной записи повторно выполняется п. 2.

Полученная таким образом запись является двоичной записью искомого числа R. Например, для исходного числа 6₁₀ = 110₂ результатом является число 96₁₀ = 1100000₂, а для исходного числа 4₁₀ = 100₂ результатом является число 79₁₀ = 1001111₂. Найдите минимальное число R, большее, чем 1500, которое может получится в результате работы алгоритма.

Решение

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

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

mn = 10000
for n in range(1, 200):
    for i in range(2):
        z = n
        k = 0
        while z > 0:
            k += z % 2
            z //= 2
        z = n * 4
        if k % 2 == 1:
            z += 3
        k1 = 0
        while z > 3:
            k1 += 1
            z //= 2
        if k % 2 == 0:
            n = n * 4 - z * 2 ** k1 + 3 * 2 ** k1
        else:
            n = n * 4 + 3 - z * 2 ** k1 + 2 * 2 ** k1
    if n > 1500:
        mn = min(mn, n)
print(mn)

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

mn = 10000
for n in range(1, 200):
    s = bin(n)[2:]
    for i in range(2):
        if s.count('1') % 2 == 0:
            s += '00'
            s = '11' + s[2:]
        else:
            s += '11'
            s = '10' + s[2:]
    r = int(s, 2)
    if r > 1500:
        mn = min (mn, r)
print(mn)

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

var
    n, r, z, k, k1, i, min: Integer;
begin
    min := 10000;
    for n := 1 to 199 do
    begin
        r := n;
        for i := 1 to 2 do
        begin
            z := r;
            k := 0;
            while z > 0 do
            begin
                k := k + z mod 2;
                z := z div 2;
            end;
            z := r * 4;
            if k mod 2 = 1 then
                z := z + 3;
            k1 := 0;
            while z > 3 do
            begin
                k1 := k1 + 1;
                z := z div 2;
            end;
            if k mod 2 = 0 then
                r := r * 4 - z * round(power(2, k1)) + 3 * round(power(2, k1))
            else
                r := r * 4 + 3 - z * round(power(2, k1)) + 2 * round(power(2, k1));
        end;
        if (r > 1500) and (r < min) then
            min := r;
    end;
    Writeln(min);
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;

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, i, min: Integer;
    s: String;
begin
    min := 10000;
    for n := 1 to 199 do
    begin
        s := Bin(n);
        for i := 1 to 2 do
        begin
            if Count(s, '1') mod 2 = 0 then
            begin
                s := s + '00';
                s := '11' + s[3:];
            end
            else
            begin
                s := s + '11';
                s := '10' + s[3:];
            end
        end;
        r := Int(s, 2);
        if (r > 1500) and (r < min) then
            min := r;
    end;
    Writeln(min);
end.

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

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    int min = 10000;
    for (int n = 1; n < 200; n++)
    {
        int r = n;
        for (int i = 0; i < 2; i++)
        {
            int z = r, k = 0;
            while (z > 0)
            {
                k += z % 2;
                z /= 2;
            }
            z = r * 4;
            if (k % 2 == 1)
                z += 3;
            int k1 = 0;
            while (z > 3)
            {
                k1++;
                z /= 2;
            }
            if (k % 2 == 0)
                r = r * 4 - z * (int)pow(2, k1) + 3 * (int)pow(2, k1);
            else
                r = r * 4 + 3 - z * (int)pow(2, k1) + 2 * (int)pow(2, k1);
        }
        if (r > 1500 && r < min)
            min = r;
    }
    cout << min << endl;
}

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 = 1; n < 200; n++)
    {
        string s = bin(n);
        for (int i = 0; i < 2; i++)
            if (count(s, '1') % 2 == 0)
            {
                s += "00";
                s = "11" + s.substr(2, s.length() - 2);
            }
            else
            {
                s += "11";
                s = "10" + s.substr(2, s.length() - 2);
            }
        int r = to_int(s, 2);
        if (r > 1500 && r < min)
            min = r;
    }
    cout << min << endl;
}

Ответ

1503