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

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

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

Например, для исходного числа 13 двоичные коды цифр: 1 = 00012, 3 = 00112. С добавленными битами чётности: 00011 и 00110, результат шага 1: 0001100110. Заменяем два левых разряда на 1 и добавляем справа 0: 10110011002 = 716.

Укажите минимальное N, после обработки которого с помощью этого алгоритма получится 674890.

Решение

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

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

for n in range(1, 10000):
    s = ''
    z = n
    while z > 0:
        s1 = bin(z % 10)[2:]
        s = '0' * (4 - len(s1)) + s1 + str(s1.count('1') % 2) + s
        z //= 10
    s = '1' + s[2:] + '0'
    if int(s, 2) == 674890:
        print(n)
        break

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

for n in range(1, 10000):
    r = 0
    z = n
    p = 1
    while z > 0:
        d = z % 10
        k = 0
        x = d
        while x > 0:
            k += x % 2
            x //= 2
        d = d * 2 + k % 2
        r += d * p
        p *= 32
        z //= 10
    p //= 4
    r = (r % p + p) * 2
    if r == 674890:
        print(n)
        break

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, z: Integer;
    s, s1: String;
begin
    for n := 1 to 9999 do
    begin
        s := '';
        z := n;
        while z > 0 do
        begin
            s1 := Bin(z mod 10);
            while(s1.Length < 4) do
                s1 := '0' + s1;
            s := s1 + IntToStr(Count(s1, '1') mod 2) + s;
            z := z div 10;
        end;
        s := '1' + s[3:] + '0';
        if Int(s, 2) = 674890 then
        begin
            Writeln(n);
            break;
        end;
    end;
end.

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

var
    n, r, x, z, p, d, k: Integer;
begin
    for n := 1 to 9999 do
    begin
        r := 0;
        z := n;
        p := 1;
        while z > 0 do
        begin
            d := z mod 10;
            k := 0;
            x := d;
            while x > 0 do
            begin
                k += x mod 2;
                x := x div 2;
            end;
            d := d * 2 + k mod 2;
            r := r + d * p;
            p := p * 32;
            z := z div 10;
        end;
        p := p div 4;
        r := (r mod p + p) * 2;
        if r = 674890 then
        begin
            Writeln(n);
            break;
        end;
    end;
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()
{
    for (int n = 1; n < 10000; n++)
    {
        string s = "";
        int z = n;
        while (z > 0)
        {
            string s1 = bin(z % 10);
            while (s1.length() != 4)
                s1 = '0' + s1;
            s = s1 + to_string(count(s1, '1') % 2) + s;
            z /= 10;
        }
        s = '1' + s.substr(2, s.length() - 2) + '0';
        if (to_int(s, 2) == 674890)
        {
            cout << n << endl;
            break;
        }
    }
}

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

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    for (int n = 1; n < 10000; n++)
    {
        int r = 0, z = n, p = 1;
        while (z > 0)
        {
            int d = z % 10, k = 0, x = d;
            while (x > 0)
            {
                k += x % 2;
                x /= 2;
            }
            d = d * 2 + k % 2;
            r += d * p;
            p *= 32;
            z /= 10;
        }
        p /= 4;
        r = (r % p + p) * 2;
        if (r == 674890)
        {
            cout << n << endl;
            break;
        }
    }
}

Ответ

5482