Задание 5. Информатика. ЕГЭ. Шастин. 29.08.2024

Просмотры: 543
Изменено: 1 февраля 2025

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

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

Например, для исходного числа \(4 = 100_2\) результатом является число \(10001_2 = 17\), а для исходного числа \(5 = 101_2\) это число \(10111_2 = 23\).

Укажите минимальное число \(R\), большее \(61\), которое могло получиться в результате работы данного алгоритма.

В ответе запишите это число в десятичной системе счисления.

Решение:

Python


def R(N):
    t = bin(N)[2:]
    q = t.count('1')
    t += '01' if q % 2 else '11'
    return int(t, 2)

ans = 10*10
for N in range(6, 100):
    if R(N) > 61:
        ans = min(ans, R(N))
        
print(ans)

C++ (через побитовые операции)


#include<iostream>

using namespace std;

int digs(int N) {
    int d = 0;
    while (N) {
        d += N & 1;
        N >>= 1;
    }
    return d;
}

int R(int N) {
    N <<= 2;
    N += (digs(N) & 1) ? 1 : 3;
    return N;
}

int32_t main() {
    int min_R = 1000000;
    for(int i = 6; i < 100; i++)
        if(R(i) > 61)
            min_R = min(R(i), min_R);
    cout << min_R << '\n';
}

Ответ: \(63\)