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

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

Строится двоичная запись числа N.
К этой записи дописываются разряды по следующему правилу. Если сумма двоичных разрядов кратна 4, слева дописывается 10, иначе 11.
К полученной записи справа дописывается еще один разряд – 0, если полученное двоичное число нечетное, 1 в обратном случае.
Полученная таким образом запись является двоичной записью искомого числа R.

Например, для числа 13 = 1101₂ получается 1111010₂ = 122, для числа 10 = 1010₂ получается 1110101₂ = 117. Укажите максимальное число N, для которого значение R не превышает 250. В ответе это число запишите в десятичной системе счисления.

Решение

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

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

mx  = 0
for n in range(1, 100):
    s = bin(n)[2:]
    if s.count('1') % 4 == 0:
        s = '10' + s
    else:
        s = '11' + s;
    if s[-1] == '0':
        s += '1'
    else:
        s += '0'
    r = int(s, 2)
    if r <= 250:
        mx = n
print(mx)

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

mx = 0
for n in range(1, 100):
    k = 0
    z = n
    while z > 0:
        k += z % 2
        z //= 2
    z = 1
    while z <= n:
        z *= 2        
    if k % 4 == 0:
        r = n + z * 2
    else:
        r = n + z * 3
    if r % 2 == 0:
        r = r * 2 + 1
    else:
        r *=2
    if r <= 250:
        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: Integer;
    s: String;
begin
    max := 0;
    for n := 1 to 99 do
    begin
        s := Bin(n);
        if Count(s, '1') mod 4 = 0 then
            s := '10' + s
        else
            s := '11' + s;
        if s[s.Length] = '0' then
            s := s + '1'
        else
            s := s + '0';
        r := Int(s, 2);
        if (r <= 250) then
          max := n;
    end;
    Writeln(max);
end.

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

var
    n, max, r, k, z: Integer;
begin
    max := 0;
    for n := 1 to 99 do
    begin
        k := 0;
        z := n;
        while z > 0 do
        begin
            k := k + z mod 2;
            z := z div 2;
        end;
        z := 1;
        while z <= n do
            z := z * 2;
        if k mod 4 = 0 then
            r := n + z * 2
        else
            r := n + z * 3;
        if r mod 2 = 0 then
            r := r * 2 + 1
        else
            r := r * 2;
        if r <= 250 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);
        if (count(s, '1') % 4 == 0)
            s = "10" + s;
        else
            s = "11" + s;
        if (s[s.length() - 1] == '0')
            s += '1';
        else
            s += '0';
        int r = to_int(s, 2);
        if (r <= 250)
            max = n;
    }
    cout << max << endl;
}

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

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