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

Страница задачи 6283

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

Строится двоичная запись числа N.
Далее эта запись обрабатывается по следующему правилу:
1. если N делится на 10, то в конец этой записи дописывается четыре последние цифры двоичной записи;
2. если N не делится на 10, то последняя цифра числа N возводится в квадрат, делится нацело на 2, переводится в двоичную запись и дописывается в конец двоичной записи числа N.
Полученная таким образом запись является двоичной записью искомого числа R.

Например, для исходного числа 11₁₀ = 1011₂ результатом является число 10110₂ = 22₁₀, а для исходного числа 20₁₀ = 10100₂ результатом является число 101000100₂ = 324₁₀.

Укажите количество значений числа N, после обработки которого с помощью этого алгоритма получается число R, меньшее 680. В ответе запишите это число в десятичной системе счисления.

Решение

Приведем реализацию данного алгоритма с обработкой чисел через строки и через эквивалентные целочисленные операции. Для манипуляций через целочисленные операции требуется отличное понимание систем счисления.

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

k = 0
for n in range(11, 1000):
    s = bin(n)[2:]
    if n % 10 == 0:
        s += s[-4:]
    else:
        s += bin((n % 10) ** 2 // 2)[2:]
    r = int(s, 2)
    if r < 680:
        k += 1
print(k)

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

k = 0
for n in range(11, 1000):
    if n % 10 == 0:
        r = n * 16 + n % 16
    else:
        z = (n % 10) ** 2 // 2
        m = 2
        while m <= z:
            m *= 2
        r = n * m + z
    if r < 680:
        k += 1
print(k)

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, k, r: Integer;
    s: String;
begin
    k := 0;
    for n := 11 to 999 do
    begin
        s := Bin(n);
        if n mod 10 = 0 then
            s := s + s[s.Length - 3:]
        else
            s := s + Bin((n mod 10) * (n mod 10) div 2);
        r := Int(s, 2);
        if r < 680 then
            k := k + 1;
    end;
    Writeln(k);
end.

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

var
    n, r, k, z, m: Integer;
begin
    k := 0;
    for n := 11 to 999 do
    begin
        if n mod 10 = 0 then
            r := n * 16 + n mod 16
        else
        begin
            z := (n mod 10) * (n mod 10) div 2;
            m := 2;
            while m <= z do
                m := m * 2;
            r := n * m + z;
        end;
        if r < 680 then
            k := k + 1;
    end;
    Writeln(k);
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 k = 0;
    for (int n = 11; n < 1000; n++)
    {
        string s = bin(n);
        if (n % 10 == 0)
            s += s.substr(s.length() - 4, 4);
        else
            s += bin((n % 10) * (n % 10) / 2);
        int r = to_int(s, 2);
        if (r < 680)
            k++;
    }
    cout << k << endl;
}

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

#include <iostream>
using namespace std;
int main()
{
    int k = 0;
    for (int n = 11; n < 1000; n++)
    {
        int r;
        if (n % 10 == 0)
            r = n * 16 + n % 16;
        else
        {
            int z = (n % 10) * (n % 10) / 2;
            int m = 2;
            while (m <= z)
                m *= 2;
            r = n * m + z;
        }
        if (r < 680)
            k++;
    }
    cout << k << endl;
}