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

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

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

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

Решение

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

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

mx = 0
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:
        mx = max (mx, r)
print(mx)

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

mx = 0
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:
        mx = max(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, r, i, max: Integer;
    s: String;
begin
    max := 0;
    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 > max) then
            max := r;
    end;
    Writeln(max);
end.

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

var
    n, r, z, k, k1, i, max: Integer;
begin
    max := 0;
    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 > max) then
            max := r;
    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 < 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 > max)
            max = r;
    }
    cout << max << endl;
}

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

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    int max = 0;
    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 > max)
            max = r;
    }
    cout << max << endl;
}

Ответ

1475