ПРОШУ ПОМОГИТЕ С ДЗ

Question

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом: 
 
1. Строится двоичная запись числа N. 
 
2. Далее эта запись обрабатывается по следующему правилу: 
 
  а) если сумма цифр в двоичной записи числа чётная, то к этой записи справа дописывается 0, а затем три левых разряда заменяются на 101; 
 
  б) если сумма цифр в двоичной записи числа нечётная, то к этой записи справа дописывается 11, а затем два левых разряда заменяются на 10. 
 
3. Полученная таким образом запись является двоичной записью искомого числа R. 
 
Например, для исходного числа 610 = 1102 результатом является число 10102 = 1010, а для исходного числа 410 = 1002 результатом является число 100112 = 1910. 
 
Укажите минимальное число N, после обработки которого с помощью этого алгоритма получается число R, большее 68. В ответе запишите это число в десятичной системе счисления.

Алексей Комолов · Answer

Для решения данной задачи сначала необходимо проанализировать алгоритм.  
 
1. Преобразование числа N в двоичную запись
2. Определение суммы цифр двоичной записи:
      - Если сумма четная: 
          - К записи добавляется `0`, и три левых разряда заменяются на `101`. 
      - Если сумма нечетная: 
          - К записи добавляется `11`, и два левых разряда заменяются на `10`. 
 
3. Преобразованная запись становится числом R
 
Теперь рассмотрим, как это работает на примерах, и найдем минимальное число N, для которого R > 68. 
 
Примеры 
 
- N = 1 (1 в двоичном виде): 
    - Двоичная запись: `1` (сумма = 1, нечетная) 
    - Обработка: `1` + `11` → `101` (заменяем 1 на 10) 
    - R = 5 (меньше 68) 
 
- N = 2 (10 в двоичном виде): 
    - Двоичная запись: `10` (сумма = 1, нечетная) 
    - Обработка: `10` + `11` → `1011` (заменяем 10 на 10) 
    - R = 11 (меньше 68) 
 
- N = 3 (11 в двоичном виде): 
    - Двоичная запись: `11` (сумма = 2, четная) 
    - Обработка: `11` + `0` → `1100` (заменяем 11 на 101) 
    - R = 12 (меньше 68) 
 
- N = 4 (100 в двоичном виде): 
    - Двоичная запись: `100` (сумма = 1, нечетная) 
    - Обработка: `100` + `11` → `10011` (заменяем 10 на 10) 
    - R = 19 (меньше 68) 
 
- N = 5 (101 в двоичном виде): 
    - Двоичная запись: `101` (сумма = 2, четная) 
    - Обработка: `101` + `0` → `10100` (заменяем 101 на 101) 
    - R = 20 (меньше 68) 
 
- N = 6 (110 в двоичном виде): 
    - Двоичная запись: `110` (сумма = 2, четная) 
    - Обработка: `110` + `0` → `11000` (заменяем 110 на 101) 
    - R = 24 (меньше 68) 
 
- N = 7 (111 в двоичном виде): 
    - Двоичная запись: `111` (сумма = 3, нечетная) 
    - Обработка: `111` + `11` → `11111` (заменяем 11 на 10) 
    - R = 31 (меньше 68) 
 
- N = 8 (1000 в двоичном виде): 
    - Двоичная запись: `1000` (сумма = 1, нечетная) 
    - Обработка: `1000` + `11` → `100011` (заменяем 10 на 10) 
    - R = 35 (меньше 68) 
 
- N = 9 (1001 в двоичном виде): 
    - Двоичная запись: `1001` (сумма = 2, четная) 
    - Обработка: `1001` + `0` → `100100` (заменяем 100 на 101) 
    - R = 36 (меньше 68) 
 
- N = 10 (1010 в двоичном виде): 
    - Двоичная запись: `1010` (сумма = 2, четная) 
    - Обработка: `1010` + `0` → `10100` (заменяем 101 на 101) 
    - R = 40 (меньше 68) 
 
- N = 11 (1011 в двоичном виде): 
    - Двоичная запись: `1011` (сумма = 3, нечетная) 
    - Обработка: `1011` + `11` → `101111` (заменяем 10 на 10) 
    - R = 43 (меньше 68) 
 
- N = 12 (1100 в двоичном виде): 
    - Двоичная запись: `1100` (сумма = 2, четная) 
    - Обработка: `1100` + `0` → `11000` (заменяем 110 на 101) 
    - R = 48 (меньше 68) 
 
- N = 13 (1101 в двоичном виде): 
    - Двоичная запись: `1101` (сумма = 3, нечетная) 
    - Обработка: `1101` + `11` → `110111` (заменяем 11 на 10) 
    - R = 55 (меньше 68) 
 
- N = 14 (1110 в двоичном виде): 
    - Двоичная запись: `1110` (сумма = 3, нечетная) 
    - Обработка: `1110` + `11` → `111011` (заменяем 11 на 10) 
    - R = 59 (меньше 68) 
 
- N = 15 (1111 в двоичном виде): 
    - Двоичная запись: `1111` (сумма = 4, четная) 
    - Обработка: `1111` + `0` → `111100` (заменяем 111 на 101) 
    - R = 60 (меньше 68) 
 
- N = 16 (10000 в двоичном виде): 
    - Двоичная запись: `10000` (сумма = 1, нечетная) 
    - Обработка: `10000` + `11` → `1000011` (заменяем 10 на 10) 
    - R = 67 (меньше 68) 
 
- N = 17 (10001 в двоичном виде): 
    - Двоичная запись: `10001` (сумма = 2, четная) 
    - Обработка: `10001` + `0` → `1000100` (заменяем 100 на 101) 
    - R = 68 (равно 68) 
 
- N = 18 (10010 в двоичном виде): 
    - Двоичная запись: `10010` (сумма = 2, четная) 
    - Обработка: `10010` + `0` → `1001000` (заменяем 100 на 101) 
    - R = 72 (больше 68) 
 
Таким образом, минимальное значение N, для которого R > 68, равно 18.