Задание 5. Информатика. ЕГЭ. Поляков-148

Просмотры: 71
Изменено: 25 ноября 2024

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

  1. Строится двоичная запись числа \(N\).
  2. К этой записи дописываются справа ещё два разряда по следующему правилу:
    а) складываются все цифры двоичной записи, и остаток от деления суммы на \(2\) дописывается в конец числа (справа). Например, запись \(11100\) преобразуется в запись \(111001\);
    б) над этой записью производятся те же действия — справа дописывается остаток от деления суммы цифр на \(2\).
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа \(N\)) является двоичной записью искомого числа \(R\). Укажите такое наименьшее число \(R\), которое превышает \(130\) и может являться результатом работы алгоритма. В ответе это число запишите в десятичной системе счисления.

Решение:

С++


#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int sum_digits(int N) {
    int s = 0;

    for(; N; s += N & 1, N>>=1) ;

    return s;
}

int R(int N) {
    for(int i = 0; i < 2; i++) 
        N = (N<<1) + sum_digits(N) % 2;
    return N;
}

int32_t main() {
    vector<int> ans;
    for(int N = 1; N < 1000; N++)
        {
            int tmp = R(N);
            if(tmp > 130)
                ans.push_back(tmp);
        }
    cout << *min_element(ans.begin(), ans.end()) << '\n';
}

Ответ: \(132\)