Демоверсия егэ информатика 2021 решение

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

1001110

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

int('10011',2)

• Получим 19.

Ответ: 19

✎ Способ 1 (программный):
Pascalabc.net:

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

begin var s1 := 1; while true do // внешний цикл, бесконечный begin var s := s1; // --- код из условия задания --- // var n := 1; while s < 51 do begin s := s + 5; n := n * 2 end; if n = 64 then // если найдено, то выводим соответствующее s begin print(s1); break; // выход из бесконечного цикла end; s1 := s1 + 1; // end; end.

begin var s1 := 1; while true do // внешний цикл, бесконечный begin var s := s1; // --- код из условия задания --- // var n := 1; while s < 51 do begin s := s + 5; n := n * 2 end; if n = 64 then // если найдено, то выводим соответствующее s begin print(s1); break; // выход из бесконечного цикла end; s1 := s1 + 1; // end; end.

Пояснение:

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

Бейсик:

Python: s1 = 1 while True: # внешний цикл, бесконечный s = s1 # --- код из условия задания --- n = 1 while s < 51: s = s + 5 n = n * 2 # --- конец кода из условия задания --- if n == 64: print(s1) break s1 += 1 s1 = 1 while True: # внешний цикл, бесконечный s = s1 # --- код из условия задания --- n = 1 while s < 51: s = s + 5 n = n * 2 # --- конец кода из условия задания --- if n == 64: print(s1) break s1 += 1

С++:

Ответ: 21

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

PascalABC.net: 1 2 3 4 5 6 7 8 9 10 11 12 begin var n:=0; var str:='школа'; for var s1:=1 to length(str) do for var s2:=1 to length(str) do for var s3:=1 to length(str) do begin if (str[s1]+str[s2]+str[s3]).Count(x->x='к')=1 then n+=1; end; print(n) end. begin var n:=0; var str:='школа'; for var s1:=1 to length(str) do for var s2:=1 to length(str) do for var s3:=1 to length(str) do begin if (str[s1]+str[s2]+str[s3]).Count(x->x='к')=1 then n+=1; end; print(n) end.

Python: 1 2 3 4 5 6 7 8 n = 0 str = 'школа' for s1 in str: for s2 in str: for s3 in str: if (s1 + s2 + s3).count('к')==1: n += 1 print(n) n = 0 str = 'школа' for s1 in str: for s2 in str: for s3 in str: if (s1 + s2 + s3).count('к')==1: n += 1 print(n)

С++: 1

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

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

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.

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:

1 2 3 4 5 6 7 8 9 10 11

begin var s: string := '8' * 70; while (s.contains('2222')) or (s.contains('8888')) do begin if (s.contains('2222')) then s := s.replace('2222', '88') else s := s.replace('8888', '22'); end; writeln(s); end.

begin var s: string := '8' * 70; while (s.contains('2222')) or (s.contains('8888')) do begin if (s.contains('2222')) then s := s.replace('2222', '88') else s := s.replace('8888', '22'); end; writeln(s); end.

Питон:

1 2 3 4 5 6 7

s = 70 * '8' while "2222" in s or "8888" in s: if "2222" in s: s = s.replace( "2222", "88", 1 ) else: s = s.replace( "8888", "22", 1 ) print(s)

s = 70 * '8' while "2222" in s or "8888" in s: if "2222" in s: s = s.replace( "2222", "88", 1 ) else: s = s.replace( "8888", "22", 1 ) print(s)

begin
  var k := 0;
  var x: Biginteger;
  x := Biginteger.Pow(49, 7) + Biginteger.Pow(7, 21) - 7;
  // в получившемся числе рассматриваем каждую цифру в 7-й системе сч.
  while x > 0 do
  begin
    if x mod 7 = 6 then k += 1; // если цифра = 6, то считаем ее
    x := x div 7; // убираем разряд числа в 7-й системе сч.
  end;
  println(k);
end.

x = 49**7 + 7**21 - 7
k = 0
# в получившемся числе рассматриваем каждую цифру в 7-й системе сч.
while x: 
    if x % 7 == 6: # если цифра = 6, то считаем ее
        k += 1
    x //= 7 # убираем разряд числа в 7-й системе сч.
print( k )

Ответ: 13

1

Питон:

1
2
3
4
5
6

for A in range(1,1000):
  OK = 1
  for x in range(1,1000):
    OK *= (x % A != 0) <= ((x % 6 == 0) <= (x % 9 != 0))
  if OK:
    print( A )

C++:

1

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

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

¬А → (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

1
2
3
4
5
6
7
8
9
10
11
12
13

function F(n: integer): integer;
begin
  if n <= 1 then
    F := 1;
  if n mod 2 = 0 then
    F := n + F(n - 1);
  if (n > 1) and (n mod 2 <> 0) then
    F := 2 * F(n - 2)
end;
 
begin
  print(F(26))
end.

Питон:

1
2
3
4
5
6
7
8

def F( n ):
   if n <= 1: 
      return 1
   if (n % 2 == 0):
      return n + F(n-1)
   if (n>1 and n % 2 != 0):
      return 2 * F(n-2)
print (F(26))

C++:

1

Ответ: 4122

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

Паскаль:

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

var i, k, max: integer;   begin k := 0; max := 0; for i := 1016 to 7937 do begin if (i mod 3 = 0) and (i mod 7 > 0) and (i mod 17 > 0) and (i mod 19 > 0) and (i mod 27 > 0) then begin max:= i; inc(k); end; end; writeln(k, ' ', max) end.

var i, k, max: integer; begin k := 0; max := 0; for i := 1016 to 7937 do begin if (i mod 3 = 0) and (i mod 7 > 0) and (i mod 17 > 0) and (i mod 19 > 0) and (i mod 27 > 0) then begin max:= i; inc(k); end; end; writeln(k, ' ', max) end.

PascalABC.NET:

1 2 3 4

begin var s := Range( 1017, 7937, 3).Where( i -> not i.DivsAny(7, 17, 19, 27) ); print( s.Count, s.Max ); end.

begin var s := Range( 1017, 7937, 3).Where( i -> not i.DivsAny(7, 17, 19, 27) ); print( s.Count, s.Max ); end.

Питон:

1 2 3

a = [n for n in range(1016,7937+1) if (n%3==0 and n%7!=0 and n%17!=0 and n%19!=0 and n%27!=0)] print(len(a),max(a))

a = [n for n in range(1016,7937+1) if (n%3==0 and n%7!=0 and n%17!=0 and n%19!=0 and n%27!=0)] print(len(a),max(a))

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

C++:

1 2 3 4 5 6 7 8 9 10 11 12 13

#include <iostream> int main() { int count = 0; int maxGood = 0; for(int n=1016; n<=7937; n++) if( (n % 3 == 0) and (n % 7 != 0) and (n % 17 != 0) and (n % 19 != 0) and (n % 27 != 0) ) { maxGood = n; count += 1; } std::cout << count << " " << maxGood; }

#include <iostream> int main() { int count = 0; int maxGood = 0; for(int n=1016; n<=7937; n++) if( (n % 3 == 0) and (n % 7 != 0) and (n % 17 != 0) and (n % 19 != 0) and (n % 27 != 0) ) { maxGood = n; count += 1; } std::cout << count << " " << maxGood; }

✎ Решение с помощью 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)

• Продолжаем работать с той же таблицей, что и в задании 19. Выделим все проигрышные позиции (из которых можно походить только в выигрышные позиции для соперника, т.е. в выделенные ячейки):

Ответ: 31 34

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

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

Ответ: 30

Паскаль:

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

var f: text; i, k, max: integer; s: string;   begin assign(f, 'D:\24.txt'); reset(f); readln(f, s); max := 1; k := 1; // кол-во подряд идущих for i := 2 to length(s) do begin if s[i] <> s[i - 1] then begin inc(k); if k > max then max := k; end else k := 1; end; write(max) end.

var f: text; i, k, max: integer; s: string; begin assign(f, 'D:\24.txt'); reset(f); readln(f, s); max := 1; k := 1; // кол-во подряд идущих for i := 2 to length(s) do begin if s[i] <> s[i - 1] then begin inc(k); if k > max then max := k; end else k := 1; end; write(max) end.

Python:

1 2 3 4 5 6 7 8 9 10 11

f=open('D:/24.txt') s=f.readline() m=1 k=1 for i in range(1,len(s)): if s[i]!=s[i-1]: k+=1 m=max(k,m) else: k=1 print(m)

f=open('D:/24.txt') s=f.readline() m=1 k=1 for i in range(1,len(s)): if s[i]!=s[i-1]: k+=1 m=max(k,m) else: k=1 print(m)

PascalABC.net: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 begin var divs := new integer[2]; var divCount := 2; for var n := 174457 to 174505 do begin var i := 0; // для индекса массива for var d := 2 to n-1 do begin if n mod d = 0 then begin if i < divCount then // чтобы индекс не выходил за границы массива divs[i] := d; inc(i); end; if i > divCount then break; end; if i = divCount then println(divs) end; end. begin var divs := new integer[2]; var divCount := 2; for var n := 174457 to 174505 do begin var i := 0; // для индекса массива for var d := 2 to n-1 do begin if n mod d = 0 then begin if i < divCount then // чтобы индекс не выходил за границы массива divs[i] := d; inc(i); end; if i > divCount then break; end; if i = divCount then println(divs) end; end.

Python: 1 2 3 4 5 6 7 8 9 divCount = 2 # нужное количество делителей for n in range(174457,174505+1): divs = [] # чистим список делителей for d in range(2,n): # перебор делителей if n % d == 0: divs = divs + [d] # добавляем делитель в список if len(divs) > divCount: break if len(divs) == divCount: print( divs ) divCount = 2 # нужное количество делителей for n in range(174457,174505+1): divs = [] # чистим список делителей for d in range(2,n): # перебор делителей if n % d == 0: divs = divs + [d] # добавляем делитель в список if len(divs) > divCount: break if len(divs) == divCount: print( divs )

С++: 1

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

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

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

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

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

PascalABC.net: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 begin var divCount := 2; for var n := 174457 to 174505 do begin var divs := new List<integer>; for var d := 2 to round(sqrt(n)) do if n mod d = 0 then begin divs.Add(d); if d <> n div d then divs.Add(n div d); if divs.Count > divCount then break; end; if divs.Count = divCount then Println(divs[0], divs[1]); end; end. begin var divCount := 2; for var n := 174457 to 174505 do begin var divs := new List<integer>; for var d := 2 to round(sqrt(n)) do if n mod d = 0 then begin divs.Add(d); if d <> n div d then divs.Add(n div d); if divs.Count > divCount then break; end; if divs.Count = divCount then Println(divs[0], divs[1]); end; end.

Python: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 from math import sqrt   for n in range(174457, 174505+1): divs = [] q = int(sqrt(n)) for d in range(2,q+1): # перебор делителей if n % d == 0: if d == n//d: # если точный квадратный корень divs = divs + [d] else: divs = divs + [d, n//d] if len(divs) > 2: break # если превысили кол-во делителей - прерываем цикл if len(divs) == 2: print(divs) # вывод делителей from math import sqrt for n in range(174457, 174505+1): divs = [] q = int(sqrt(n)) for d in range(2,q+1): # перебор делителей if n % d == 0: if d == n//d: # если точный квадратный корень divs = divs + [d] else: divs = divs + [d, n//d] if len(divs) > 2: break # если превысили кол-во делителей - прерываем цикл if len(divs) == 2: print(divs) # вывод делителей

С++: 1

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

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

1 2 3 4

for n in range(174457, 174505+1): divs = [d for d in range(2, n) if n % d == 0] # range(2, n), т.к. два делителя, не считая 1 и самого числа if len(divs) == 2: print( *divs )

for n in range(174457, 174505+1): divs = [d for d in range(2, n) if n % d == 0] # range(2, n), т.к. два делителя, не считая 1 и самого числа if len(divs) == 2: print( *divs )