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

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

Строится двоичная запись числа N.
К этой записи дописываются разряды по следующему правилу. Если число кратно 3, то справа дописывается 010, иначе справа дописывается двоичная запись результата умножения 5 на остаток от деления числа N на 3.
Полученная таким образом запись является двоичной записью искомого числа R.

Например, для числа 13 = 1101₂ получается 1101101₂ = 109, для числа 9 двоичная запись 1001₂ преобразуется в 1001010₂ = 74. Укажите значение N, в результате обработки которого будет получено минимально возможное четное значение R, большее 300. Если таких значений несколько, приведите минимальное подходящее значение.

Решение

Для данной задачи даже на Python решение через эквивалентные целочисленные операции не превышает по объему кода решение через использование строк.

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

mn = 1000
mnn = 0
for n in range(1, 100):
    s = bin(n)[2:]
    if n % 3 == 0:
        s += '010'
    else:
        s += bin(n % 3 * 5)[2:]
    r = int(s, 2)
    if r > 300 and r % 2 == 0 and r < mn:
        mn = r
        mnn = n
print(mnn)

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

mn = 1000
mnn = 0
for n in range(1, 100):
    if n % 3 == 0:
        r = n * 8 + 2
    elif n % 3 == 1:
        r = n * 8 + 5
    else:
        r = n * 16 + 10
    if r > 300 and r % 2 == 0 and r < mn:
        mn = r
        mnn = n
print(mnn)

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, min, minn, r: Integer;
    s: String;
begin
    min := 1000;
    minn := 0;
    for n := 1 to 99 do
    begin
        s := Bin(n);
        if n mod 3 = 0 then
            s := s + '010'
        else
            s := s + Bin(n mod 3 * 5);
        r := Int(s, 2);
        if (r > 300) and (r mod 2 = 0) and (r < min) then
        begin
            min := r;
            minn := n;
        end;
    end;
    Writeln(minn);
end.

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

var
    n, min, minn, r: Integer;
begin
    min := 1000;
    minn := 0;
    for n := 1 to 99 do
    begin
        if n mod 3 = 0 then
          r := n * 8 + 2
        else if n mod 3 = 1 then
            r := n * 8 + 5
        else
            r := n * 16 + 10;
        if (r > 300) and (r mod 2 = 0) and (r < min) then
        begin
            min := r;
            minn := n;
        end;
    end;
    Writeln(minn);
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()
{
    int min = 1000, minn = 0;
    for (int n = 1; n < 100; n++)
    {
        string s = bin(n);
        if (n % 3 == 0)
            s += "010";
        else
            s += bin(n % 3 * 5);
        int r = to_int(s, 2);
        if (r > 300 && r % 2 == 0 && r < min)
        {
            min = r;
            minn = n;
        }
    }
    cout << minn << endl;
}

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

#include <iostream>
using namespace std;
int main()
{
    int min = 1000, minn = 0, r;
    for (int n = 1; n < 100; n++)
    {
        if (n % 3 == 0)
            r = n * 8 + 2;
        else if (n % 3 == 1)
            r = n * 8 + 5;
        else
            r = n * 16 + 10;
        if (r > 300 && r % 2 == 0 && r < min)
        {
            min = r;
            minn = n;
        }
    }
    cout << minn << endl;
}