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

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

Строится двоичная запись числа N.
Далее эта запись обрабатывается по следующему правилу:
1. если сумма цифр в двоичной записи числа чётная, то 4 младших бита инвертируются, т.е. 0 изменяется на 1, а 1 на 0;
2. если сумма цифр в двоичной записи числа нечётная, то инвертируются 4 бита в двоичных разрядах 1-4 (нумерация разрядов справа налево, начиная с 0).
Полученная таким образом запись является двоичной записью искомого числа R.

Например, для исходного числа 125 = 1111101₂ результатом является число 114 = 1110010₂ а для исходного числа 227 = 11100011₂ результатом является число 253 = 11111101₂.

Укажите число N, большее 63, после обработки которого с помощью этого алгоритма получается минимальное число R. В ответе запишите число в десятичной системе счисления.

Решение

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

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

mn = 10000
mnn = 0
for n in range(64, 230):
    z = n
    k = 0
    while z > 0:
        k += z % 2
        z //= 2
    if k % 2 == 0:
        r = n // 16 * 16 + 15 - n % 16
    else:
        r = n // 32 * 32 + 30 - n // 2 % 16 * 2 + n % 2
    if r < mn:
        mn = r
        mnn = n
print(mnn)

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

mn = 10000
mnn = 0
for n in range(64, 230):
    s = bin(n)[2:]
    if s.count('1') % 2 == 0:
        s1 = s[:-4]
        for i in s[-4:]:
            if i == '0':
                s1 += '1'
            else:
                s1 += '0'
    else:
        s1 = s[:-5]
        for i in s[-5:-1]:
            if i == '0':
                s1 += '1'
            else:
                s1 += '0'
        s1 += s[-1]
    r = int(s1, 2)
    if r < mn:
        mn = r
        mnn = n
print(mnn)

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

var
    n, r, z, k, min, minn: Integer;
begin
    min := 10000;
    minn := 0;
    for n := 64 to 229 do
    begin
        z := n;
        k := 0;
        while z > 0 do
        begin
            k := k + z mod 2;
            z := z div 2;
        end;
        if k mod 2 = 0 then
            r := n div 16 * 16 + 15 - n mod 16
        else
            r := n div 32 * 32 + 30 - n div 2 mod 16 * 2 + n mod 2;
        if r < min then
        begin
            min := r;
            minn := n;
        end;
    end;
    Writeln(minn);
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, min, minn, i: Integer;
    s, s1: String;
begin
    min := 10000;
    minn := 0;
    for n := 64 to 229 do
    begin
        s := Bin(n);
        if Count(s, '1') mod 2 = 0 then
        begin
            s1 := s[:s.Length - 3];
            for i := s.Length - 3 to s.Length do
                if s[i] = '0' then
                    s1 := s1 + '1'
                else
                    s1 := s1 + '0';
        end
        else
        begin
            s1 := s[:s.Length - 4];
            for i := s.Length - 4 to s.Length - 1 do
                if s[i] = '0' then
                    s1 := s1 + '1'
                else
                    s1 := s1 + '0';
            s1 := s1 + s[s.Length];
        end;
        r := Int(s1, 2);
        if r < min then
        begin
            min := r;
            minn := n;
        end;
    end;
    Writeln(minn);
end.

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

#include <iostream>
using namespace std;
int main()
{
    int min = 10000, minn = 0;
    for (int n = 64; n < 230; n++)
    {
        int z = n, k = 0, r;
        while (z > 0)
        {
            k += z % 2;
            z /= 2;
        }
        if (k % 2 == 0)
            r = n / 16 * 16 + 15 - n % 16;
        else
            r = n / 32 * 32 + 30 - n / 2 % 16 * 2 + n % 2;
        if (r < min)
        {
            min = r;
            minn = n;
        }
    }
    cout << minn << 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, minn = 0;
    for (int n = 64; n < 230; n++)
    {
        string s = bin(n), s1;
        if (count(s, '1') % 2 == 0)
        {
            s1 = s.substr(0, s.length() - 4);
            for (int i = s.length() - 4; i < s.length(); i++)
                if (s[i] == '0')
                    s1 += '1';
                else
                    s1 += '0';
        }
        else
        {
            s1 = s.substr(0, s.length() - 5);
            for (int i = s.length() - 5; i < s.length() - 1; i++)
                if (s[i] == '0')
                    s1 += '1';
                else
                    s1 += '0';
            s1 += s[s.length() - 1];
        }
        int r = to_int(s1, 2);
        if (r < min)
        {
            min = r;
            minn = n;
        }
    }
    cout << minn << endl;
}