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

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

Строится двоичная запись числа N.
Если число N не делится на 2, все цифры двоичной записи инвертируются (0 заменяется на 1 и наоборот).
Все цифры полученной двоичной записи дублируются.
Полученная таким образом запись является двоичной записью искомого числа R.

Например, для числа 6 двоичная запись 110₂ преобразуется в запись 111100₂ = 60, для числа 5 двоичная запись 101₂ преобразуется в 1100₂ = 12. Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, большее чем 60.

Решение

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

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

for n in range(1, 20):
    s = bin(n)[2:]
    s1 = ''
    for i in s:
        if i == '0' and s[-1] == '0' or i == '1' and s[-1] == '1':
            s1 += '00'
        else:
            s1 += '11'
    r = int(s1, 2)
    if r > 60:
        print(n)
        break

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

for n in range(1, 20):
    z = n
    x = 1
    r = 0
    while z > 0:
        if z % 2 == 1 and n % 2 == 0 or z % 2 == 0 and n % 2 == 1:
            r += x * 3
        x *= 4
        z //= 2
    if r > 60:
        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;

var
    n, r, i: Integer;
    s, s1: String;
begin
    for n := 1 to 19 do
    begin
        s := Bin(n);
        s1 := '';
        for i := 1 to s.Length do
            if (s[i] = '0') and (s[s.Length] = '0') or
               (s[i] = '1') and (s[s.Length] = '1') then
                s1 := s1 + '00'
            else
                s1 := s1 + '11';
        r := Int(s1, 2);
        if r > 60 then
        begin
            Writeln(n);
            break;
        end;
    end;
end.

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

var
    n, r, z, x: Integer;
begin
    for n := 1 to 19 do
    begin
        z := n;
        x := 1;
        r := 0;
        while z > 0 do
        begin
            if (z mod 2 = 1) and (n mod 2 = 0) or (z mod 2 = 0) and (n mod 2 = 1) then
                r := r + x * 3;
            x := x * 4;
            z := z div 2;
        end;
        if r > 60 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 main()
{
    for (int n = 1; n < 20; n++)
    {
        string s = bin(n), s1 = "";
        for (int i = 0; i < s.length(); i++)
            if (s[i] == '0' && s[s.length() - 1] == '0' ||
                s[i] == '1' && s[s.length() - 1] == '1')
                s1 += "00";
            else
                s1 += "11";
        int r = to_int(s1, 2);
        if (r > 60)
        {
            cout << n << endl;
            break;
        }
    }
}

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

#include <iostream>
using namespace std;
int main()
{
    for (int n = 1; n < 20; n++)
    {
        int z = n, x = 1, r = 0;
        while (z > 0)
        {
            if (z % 2 == 1 && n % 2 == 0 || z % 2 == 0 && n % 2 == 1)
                r += x * 3;
            x *= 4;
            z /= 2;
        }
        if (r > 60)
        {
            cout << n << endl;
            break;
        }
    }
}