ЕГЭ по информатике 2021 — Задание 1 (Особые точки)

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

1001110

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

int('10011',2)

• Получим 19.

Ответ: 19

✎ Решение с использованием программирования:
PascalABC.NET:
Вариант 1:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

beginvar s :='8'*70;var p2 := Pos('2222',s);var p8 := Pos('8888',s);while(p2 > 0)or(p8 > 0)dobeginif p2 > 0thenbegin Delete( s, p2,4); Insert('88', s, p2 );endelsebegin Delete( s, p8,4); Insert('22', s, p8 );end; p2 := Pos('2222',s); p8 := Pos('8888',s);end;write(s);end.

begin
var s := ‘8’*70;
var p2 := Pos(‘2222’,s);
var p8 := Pos(‘8888′,s);
while (p2 > 0) or (p8 > 0) do begin
if p2 > 0 then begin
Delete( s, p2, 4 );
Insert( ’88’, s, p2 );
end
else begin
Delete( s, p8, 4 );
Insert( ’22’, s, p8 );
end;
p2 := Pos(‘2222’,s);
p8 := Pos(‘8888’,s);
end;
write(s);
end.

Вариант 2:

Питон:

Питон:

C :

✎ Решение теоретическое:

• Введем обозначения и перепишем исходную формулу:

¬А → (6 → ¬9) = 1

• Избавимся от импликации:

А ∨ ¬6 ∨ ¬9 = 1

• Будем отрицать известную часть:

¬(¬6 ∨ ¬9) = 1

• Получаем:

6 ∧ 9 = 1

• Таким образом, необходимо найти наибольшее А, на которое делятся все натуральные х, такое что эти х делятся и на 6 и на 9 одновременно:

x/A : x/6 AND x/9 

• Переберем х, которые одновременно делятся и на 6 и на 9:

х = 18, 36, 54, 72 ...

• Переберем А, начиная с наименьшего, до такого наибольшего А, которое будет делителем всех найденных х:

А = 1, 2, 3, 4, 5, ... 18

При попытке взять большее А, x равный 18 не будет делиться на такое А.

Ответ: 18

✎ Решение с использованием программирования:

Паскаль:

PascalABC.NET:

Питон:

Список a формируем, используя генератор списка: то есть в список попадут только не числа из диапазона [1016,7937], которые удовлетворяют всем перечисленным условиям: n%3==0 (число делится на 3), n%7!=0 (число не делится на 7) и т.п.

C :

✎ Решение с помощью Excel:

• Первое значение диапазона введем в ячейку A1:



• Используем прогрессию для заполнения всего диапазона числами. Для это выберите вкладку Главная и щелкните по кнопке Прогрессия:



• Столбец B будем использовать для поиска чисел, которые делятся на 3. Для этого в ячейку B1 введите формулу с рисунка:



• Двойным щелчком по маркеру заполнения скопируйте формулу на весь столбец:



• Столбец С будем использовать для поиска чисел, которые НЕ делятся на 7. Для этого в ячейку С1 введите формулу с рисунка:



• Заполните весь столбец двойным щелчком по маркеру заполнения.
• Cтолбцы D, E, F таким же образом будем использовать для поиска чисел столбца А, которые не делятся на 17, 19 и 27



• Для поиска всех истинных значений используем столбец G. В ячейку G1 введите функцию ЕСЛИ: если все значения ячеек в столбцах B-F в этой строке истинны, выводим число из А1, иначе – пустую строку:


Заполните весь столбце, используя маркер автозаполнения.

• Ячейку H1 будем использовать для подсчета таких чисел, которые удовлетворяют всем условиям, т.е. для подсчета непустых ячеек столбца G:



• Ячейку H2 будем использовать для подсчета такого наибольшего числа:

• Нарисуем таблицу, в первом столбце которой будем откладывать количество камней в первой куче, а в первой строке — количество камней во второй куче. Получим матрицу. Поскольку в первой куче количество начинается с 7, то это и будет первым значением в таблице. Во второй куче начнем с наибольшего возможного числа — 69:



• Далее будем рассуждать так: Петя может выиграть первым ходом, выполнив команду *2 (увеличить количество камней в куче в два раза), если вместо S (кол-во камней во второй куче), мы будем изменять значение, начиная от 35, до последнего возможного по условию значения 69:

7 35*2 = 77 (>=77)

• Соответственно, все значения большие 34 дадут в результате сумму, большую 76. Укажем это в таблице. означает выигрышную позицию с первого хода.
• По заданию необходимо, чтобы Петя проиграл. То есть необходимо подобрать S, из которого можно попасть в диапазон выигрышных позиций для соперника:

17 * 2 = 34 (мало, необходимо 35 и более) 18 * 2 = 36 подходит!

Ответ: 18
✍ Решение 2 (Excel):

• В столбце А отложим значения — количество камней в первой куче. Начнем с ячейки А2, в которую внесем начальное количество камней, т.е. 7. Автозаполнением продлим значения вниз до 25 примерно:
• В строке 1 таблицы (начиная с ячейки B1) отложим значения для второй кучи. Поскольку в задании говорится, что 0<=S<=69, то последним значением пусть будет 40. В дальнейшем часть таблицы можно будет удалить:





• Из двух команд, которые могут выполнять игроки, выберем наиболее сильную, т.е. благодаря которой можно быстрее достичь выигрышного диапазона и попасть в значения S>=77. Это команда удваивания количества камней, т.е. *2.
• Для каждой из ячеек полученной таблицы рассчитаем значение, полученное в результате удвоения той кучи камней, в которой большее количество камней (так как это даст бОльший результат). Например, для ячейки С5, в которой игрок имеет в первой куче 10 камней, а во второй куче 2 камня, мы бы выполнили действие 10*2 2. Т.е. удвоили бы первую кучу, т.к. в ней больше камней.
• Чтобы автоматизировать процесс необходимо использовать формулу, в которой найдем максимальное значение из двух вариантов: Максимальное из(1куча*2 2куча, 1куча 2*2куча). Выразив это в формуле Excel, получим результат, который внесем в ячейку B2:

=МАКС($A2 2*B$1;2*$A2 B$1)

• Здесь знак $ будем использовать для фиксации столбца А и строки 1 при копировании формулы.



• Скопируем формулу на всю таблицу.
• Выделим всю таблицу и используем Условное форматирование для выделения тех значений, которые попадают в выигрыш (>76):



• Выделенные значения — это значения, которые можно получить в сумме двух куч, выполнив ход из данной ячейки. И по сути, это и есть выигрышные позиции с 1 хода.
• Далее следуем логике рассуждения из предыдущего способа решения.

Ответ: 18

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



• Последующая логика рассуждений: Петя может выиграть свои вторым ходом, если он не может выиграть первым ходом, и одновременно получив позицию, выигрышную со второго хода:



(7,34) -> (8,34)
(7,31) -> (14,31)

Ответ: 31 34

✎ Решение 2 (Excel)

Ответ: 31 34

• Необходимо найти для Пети проигрышные позиции со второго хода. Это должна быть первая строка, т.к. это первый ход Пети. Первое подходящее значение — 33, из него Петя может либо сразу походить в выигрышную позицию с первого хода (7, 66), либо в выигрышную позицию со второго хода: (7,34) и (8,33).
• Но есть значение меньше 33, это значение 30:

Ваня выиграет с первого хода, если: Петя (7,60)
Ваня выиграет с последующих ходов, если: Петя (7,31), (8,30), (14,30) 

Ответ: 30

✎ Решение (оптимизированный вариант 1):

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

если число имеет ровно два делителя, отличных от единицы и самого числа, то произведение этих делителей и есть само число

• Будем использовать оптимизированный вариант программы, подходящий для «медленных» компьютеров. Для этого перебор делителей для числа n будем выполнять от 2 до √n, округлив его до ближайшего целого числа (не включая точный квадратный корень, если он существует):

вместо диапазона делителей [2; число]
использовать диапазон [2; округл(√n)]

• При переборе делителей будем определять: если делитель – это точный квадратный корень(n), то в список делителей добавлять будем только сам делитель, если нет – то добавляем пару делителей (делитель и n // делитель):

Пример:
число 8 = 2 * 4
Достаточно рассмотреть цикл от 2 до округл(√8) (=2)
если 8 делится на 2 и 8/2 не равно 2, то делители: 2 и 4 (8/2)

✎ Решение (оптимизированный вариант 2):
Python:

• Для каждого числа указанного диапазона генерируем список делителей.
• Если длина списка равна двум, выводим его.