Информатика ЕГЭ 5 задание разбор

• Заметим, что после выполнения второго пункта задания, будут получаться только четные числа! Наименьшим возможным четным числом, превышающим 129, является число 130. С ним и будем работать.
• Переведем 130 в двоичную систему счисления. Используя компьютер это можно сделать с помощью программистского режима калькулятора. Либо в консоли интерпретатора Python набрать bin(130). Получим:

13010 = 100000102

• Это двоичное число получилось из исходного двоичного, после того как дважды был добавлен остаток от деления суммы цифр на 2. Т.е.:

в обратном порядке:
было 1000001 -> стало 10000010 
еще раз то же самое: 
было 100000 -> стало 1000001 

• Значит, необходимое нам двоичное число — это 100000.
• Переведем 100000 в 10-ю систему. Для этого можно воспользоваться калькулятором, либо использовать интерпретатор Питона: int('100000',2).

1000002 = 3210

• Так как по условию у нас 4*N, то 32 делим на 4 — > 8.

• Заметим, что после второго пункта условия задачи получаются только четные числа (т.к. если число в двоичной системе заканчивается на 0, то оно четное). Таким образом, нас будут интересовать только четные числа.
• Наименьшим возможным числом, превышающим 83, является число 84. С ним и будем работать.
• Переведем 84 в двоичную систему счисления. На компьютерном ЕГЭ это можно сделать с помощью программистского режима калькулятора. Либо в консоли интерпретатора Python набрать bin(84). Получим:

84 = 1010100

• В данном числе выделенная часть — это N. Значит, необходимое нам двоичное число — это 10101. После первого пункта задачи к данному числу должна была добавиться справа единица, так как оно нечетное. А мы имеем 0. Соответственно, это оно не подходит.
• Возьмем следующее четное число — 86. Переведем его в двоичную систему счисления:

86 = 1010110

• В данном числе выделенная часть — это N. Значит, необходимое нам двоичное число — это 10101. После первого пункта задачи к данному числу должна была добавиться справа единица, так и есть: 101011. А затем добавляется 0: 1010110. Соответственно, оно подходит.

• Поскольку требуется найти наибольшее число, то возьмем наибольшее из возможных чисел, которые < 100 — это число 99. Переведем его в двоичную систему. На компьютерном ЕГЭ это можно сделать с помощью программистского режима калькулятора. Либо в консоли интерпретатора Python набрать bin(99). Получим:

99 = 11000112

• По алгоритму это число получилось путем добавления справа двух разрядов, значение которых зависит от исходного N:

1100011
  N    

• Т.е. в конце были добавлены две единицы — по алгоритму это значит, что исходное N должно в остатке при делении на 4 давать 3. Переведем найденное N в десятичную систему. Можно использовать калькулятор либо консоль пайтон: int('11000',2)

11000 = 2410

• 24 делится на 4 нацело, т.е. в конце по алгоритму должны были добавиться два разряда — 00. У нас же в конце 11. Т.е. число 99 не подходит. Проверим следующее — 98.

98 = 11000102  : 10 в конце добавлено алгоритмом
N = 110002 = 2410
24 делится нацело на 4. 
По алгоритму в конце должно быть 00, а мы имеем 10 
98 - не подходит

97 = 11000012 : 01 в конце добавлено алгоритмом
N = 110002 = 2410
24 делится нацело на 4. 
По алгоритму в конце должно быть 00, а мы имеем 01 
97 - не подходит

96 = 11000002 : 00 в конце добавлено алгоритмом
N = 110002 = 2410
24 делится нацело на 4. 
По алгоритму в конце должно быть 00, у нас 00 - верно!
96 - подходит!

Результат: 96

• В постановке задания задано R > 114. R — это результат работы алгоритма. Для того, чтобы определить наименьшее возможно N, переведем сначала 114 в двоичную систему счисления и выделим в нем три добавленные по алгоритму цифры (перевод можно выполнить в консоли Питона: bin(114))

114 = 11100102

• Проанализируем, как могло бы получиться двоичное число 114 (R) по алгоритму:

2. В полученное числе N = 1110 дублируется последняя цифра и получается 11100.
3. Поскольку число единиц (3) — нечетное, то справа добавляется 1: 111001.
4. Т.к. в полученном наборе цифр четное число единиц, то добавляем 0: 1110010

• Поскольку из числа N = 1110 по алгоритму могла получиться только такая последовательность цифр (1110010), то для получения минимального R, но большего чем R = 114, увеличим в N = 1110 самый младший разряд на единицу и рассмотрим работу алгоритма с полученным числом:

1. N = 1110 + 1 = 1111

Работа по алгоритму:
2. 11111 - дублирование последней цифры.
3. 111111 - справа дописываем единицу, т.к. в полученном числе 5 единиц (нечетное)
4. 1111110 - дописываем ноль, т.к. в полученном числе четное число единиц.

• Ответ нужно получить в десятичной системе счисления (для перевода можно воспользоваться интерпретатором Питона: int('1111110',2)):

min R = 11111102 = 12610

Результат: 126

• Результатом выполнения алгоритма является число 45. Алгоритм работает в двоичной системе счисления, поэтому переведем число:

45 = 001011012

• Пронумеруем биты слева направо, начиная с единицы. Рассмотрим каждый бит отдельно, начиная с левого бита под номером 1.
• 1. Так как биты в уменьшаемом и вычитаемом должны быть различны, то единица в результате может получится только 1 - 0, с учетом, что у разряда с единицей заняли. То есть бит:

   .
_  1 _ _ _ _ _ _ _    N инвертируемое
=  0 _ _ _ _ _ _ _    N исходное
   0 0 1 0 1 1 0 1  = 45   результат

• 2. 1 - 0 не может в результате дать 0, так как у следующей слева единицы мы заняли. Значит, 0 - 1. Чтобы не получить единицу в ответе, необходимо у нуля тоже занять:

   . .
_  1 0 _ _ _ _ _ _ 
=  0 1 _ _ _ _ _ _ 
   0 0 1 0 1 1 0 1  = 45   результат

• 3. 1 - 0 не может быть, так как у следующего слева нуля мы заняли.
  Значит 0 - 1. То есть как раз чтобы получить единицу (10 - 1 = 1), занимаем у следующих слева разрядов:

   . .
_  1 0 0 _ _ _ _ _ 
=  0 1 1 _ _ _ _ _ 
   0 0 1 0 1 1 0 1  = 45   результат

• 4. 0 - 1 не может быть. Значит, чтобы получить в результате ноль, берем 1 - 0, у единицы должно быть занято.

   . .   .
_  1 0 0 1 _ _ _ _ 
=  0 1 1 0 _ _ _ _ 
   0 0 1 0 1 1 0 1  = 45   результат

• 5. 1 - 0 не может быть. Так как слева у единицы занято. Значит, чтобы получить в результате 1, берем 0 - 1:

   . .   .
_  1 0 0 1 0 _ _ _ 
=  0 1 1 0 1 _ _ _ 
   0 0 1 0 1 1 0 1  = 45   результат

• 6. 0 - 1 не даст в ответе единицу, значит, имеем 1 - 0:

   . .   .
_  1 0 0 1 0 1 _ _ 
=  0 1 1 0 1 0 _ _ 
   0 0 1 0 1 1 0 1  = 45   результат

• 7. 0 - 1 не может быть, значит, 1 - 0. Чтобы получить в результате 0, необходимо, чтобы у 1 было занято:

   . .   .     .
_  1 0 0 1 0 1 1 _ 
=  0 1 1 0 1 0 0 _ 
   0 0 1 0 1 1 0 1  = 45   результат

• 8. Чтобы получить 1, имеем 0 - 1:

   . .   .     .
_  1 0 0 1 0 1 1 0 
=  0 1 1 0 1 0 0 1
   0 0 1 0 1 1 0 1  = 45   результат

• Полученное число (вычитаемое) и есть искомое N. Переведем его в 10-ю с.с.:

01101001 = 10510

Результат: 1

• Обозначим каждую цифру числа Y согласно заданию:

Y =    3       1       2
       x mod 7    x mod 2    x mod 5

• Сделаем выводы:

1. x mod 2 = 1 => значит, X — нечетное число
2. x mod 5 = 2 => значит, X — либо ?2, либо ?7.
3. раз x — нечетное, то из пред. пункта получаем x = ?7
4. x mod 7 = 3 => переберем все варианты:

97 - не подходит, 
87 - подходит (87 / 7 = 12, остаток = 3)
77 - не подходит,
67 - не подходит,
57 - не подходит,
47 - не подходит,
37 - не подходит,
27 - не подходит,
17 - подходит (17 / 7 = 2, остаток = 3)