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

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

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

Строится двоичная запись числа N.
Если двоичная запись задаёт нечётное число и её бит чётности равен 1, то к этой записи слева дописывается 1; в противном случае справа дописывается бит чётности.
Шаг 2 повторяется.
Полученная таким образом запись является двоичной записью искомого числа R.

Например, для исходного числа 12 = 1100₂ результатом является число 110000₂ = 48, а для исходного числа 4 = 100₂ результатом является число 10010₂ = 18. Укажите максимальное число N, после обработки которого с помощью этого алгоритма получается число R, меньшее 100.

Решение

Последовательно перебираем числа, обрабатывая их алгоритмом задачи и анализируя результат. Обработка возможна через эквивалентные целочисленные операции или через строки. Обработка через строки на C++ и PascalABC потребует дополнительных функции для перевода систем счисления.

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

mx  = 0
for n in range(1, 100):
    s = bin(n)[2:]
    for i in range(2):
        if s[-1] == '1' and s.count('1') % 2 == 1:
            s = '1' + s
        else:
            s += str(s.count('1') % 2)
    r = int(s, 2)
    if r < 100:
        mx = n
print(mx)

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

mx = 0
for n in range(1, 100):
    r = n
    for i in range(2):
        k = 0
        z = r
        while z > 0:
            k += z % 2
            z //= 2
        if r % 2 == 1 and k % 2 == 1:
            z = 1
            while z <= r:
                z *= 2
            r += z
        else:
            r = r * 2 + k % 2
    if r < 100:
        mx = n
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;

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, max, r, i: Integer;
    s: String;
begin
    max := 0;
    for n := 1 to 99 do
    begin
        s := Bin(n);
        for i := 1 to 2 do
            if (s[s.Length] = '1') and (Count(s, '1') mod 2 = 1) then
                s := '1' + s
            else
                s := s + IntToStr((Count(s, '1') mod 2));
        r := Int(s, 2);
        if (r < 100) then
          max := n;
    end;
    Writeln(max);
end.

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

var
    n, max, r, k, z, i: Integer;
begin
    max := 0;
    for n := 1 to 99 do
    begin
        r := n;
        for i := 1 to 2 do
        begin
            k := 0;
            z := r;
            while z > 0 do
            begin
                k := k + z mod 2;
                z := z div 2;
            end;
            if  (r mod 2 = 1) and (k mod 2 = 1) then
            begin
                z := 1;
                while z <= r do
                    z := z * 2;
                r := z + r;
            end
            else
                r := r * 2 + k mod 2;
        end;
        if r < 100 then
          max  := n;
    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 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 max = 0;
    for (int n = 1; n < 100; n++)
    {
        string s = bin(n);
        for (int i = 0; i < 2; i++)
            if (s[s.length() - 1] == '1' && count(s, '1') % 2 == 1)
                s = '1' + s;
            else
                s += to_string(count(s, '1') % 2);
        int r = to_int(s, 2);
        if (r < 100)
            max = n;
    }
    cout << max << endl;
}

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

#include <iostream>
using namespace std;
int main()
{
    int max = 0;
    for (int n = 1; n < 100; n++)
    {
        int r = n;
        for (int i = 0; i < 2; i++)
        {
            int k = 0, z = r;
            while (z > 0)
            {
                k += z % 2;
                z /= 2;
            }
            if (r % 2 == 1 && k % 2 == 1)
            {
                z = 1;
                while (z <= r)
                    z *= 2;
                r += z;
            }
            else
                r = r * 2 + k % 2;
        }
        if (r < 100)
            max = n;
    }
    cout << max << endl;
}