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

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

Строится двоичная запись числа N.
Если число N делится на 6, в конец двоичной записи дописывается двоичный код числа 7, иначе дописывается единица.
Если число, полученное после шага 2, делится на 3, в конец двоичной записи дописывается двоичный код числа 5, иначе дописывается единица.
Полученная таким образом запись является двоичной записью искомого числа R.

Например, для исходного числа 12₁₀ = 1100₂ (делится на 6) после шага 2 получается число 1100111₂ = 103₁₀ (не делится на 3), а после шага 3 – число 11001111₂ = 207₁₀. Определите наименьшее возможное значение N, для которого в результате работы алгоритма получается R > 300000.

Решение

Достаточно редкий случай, когда решения через строки и эквивалентные целочисленные операции не отличаются по сложности и объему кода, если не учитывать необходимых функций преобразования на C++ и PascalABC.

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

for n in range(1, 100000):
    s = bin(n)[2:]
    if n % 6 == 0:
        s += '111'
    else:
        s += '1'
    if int(s, 2) % 3 == 0:
        s += '101'
    else:
        s += '1'
    if int(s, 2) > 300000:
        print(n)
        break

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

for n in range(1, 100000):
    r = n
    if r % 6 == 0:
        r = r * 8 + 7
    else:
        r = r * 2 + 1
    if r % 3 == 0:
        r = r * 8 + 5
    else:
        r = r * 2 + 1
    if r > 300000:
        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: Integer;
    s: String;
begin
    for n := 1 to 99999 do
    begin
        s := Bin(n);
        if n mod 6 = 0 then
            s := s + '111'
        else
            s := s + '1';
        if Int(s, 2) mod 3 = 0 then
            s := s + '101'
        else
            s := s + '1';
        if Int(s, 2) > 300000 then
        begin
            Writeln(n);
            break;
        end;
    end;
end.

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

var
    n, r: Integer;
begin
    for n := 1 to 99999 do
    begin
        r := n;
        if r mod 6 = 0 then
            r := r * 8 + 7
        else
            r := r * 2 + 1;
        if r mod 3 = 0 then
            r := r * 8 + 5
        else
            r := r * 2 + 1;
        if r > 300000 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 < 100000; n++)
    {
        string s = bin(n);
        if (n % 6 == 0)
            s += "111";
        else
            s += "1";
        if (to_int(s, 2) % 3 == 0)
            s += "101";
        else
            s += "1";
        if (to_int(s, 2) > 300000)
        {
            cout << n << endl;
            break;
        }
    }
}

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

#include <iostream>
using namespace std;
int main()
{
    for (int n = 1; n < 100000; n++)
    {
        int r = n;
        if (r % 6 == 0)
            r = r * 8 + 7;
        else
            r = r * 2 + 1;
        if (r % 3 == 0)
            r = r * 8 + 5;
        else
            r = r * 2 + 1;
        if (r > 300000)
        {
            cout << n << endl;
            break;
        }
    }
}

Ответ

18750