Разбор 20 задания егэ по информатике 2020 - Помощь в подготовке к экзаменам и поступлению

Задание 20. Программирование: циклы и ветвления: Объяснение и решение демоверсии егэ по информатике 2020

Разбор 20 задания. Демоверсия егэ по информатике 2020, ФИПИ:

Ниже на нескольких языках программирования записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа: L и M.

Укажите наименьшее число x, при вводе которого алгоритм печатает сначала 6, а потом 7.

Паскаль:

var
  x, L, M: integer;
begin
  readln(x);
  L := 0;
  M := 0;
  while x > 0 do
  begin
    M := M + 1;
    if x mod 2 = 0 then
      L := L + 1;
    x := x div 2;
  end;
  writeln(L);
  writeln(M);
end.

Бейсик:

DIM X, L, M AS INTEGER
INPUT X
L = 0
M = 0
WHILE X > 0
  M = M + 1
  IF X MOD 2 = 0 THEN
     L = L + 1
  ENDIF
  X = X  2
WEND
PRINT L
PRINT M

Python:

x = int(input())
L = 0
M = 0
while x > 0:
   M = M + 1
   if x % 2 == 0:
      L = L + 1
   x = x // 2
print(L)
print(M)

С++:

#include <iostream>
using namespace std;
int main()
{
int x, L, M;
cin >> x;
L = 0;
M = 0;
while (x > 0){
  M = M + 1;
  if(x % 2 == 0){
     L = L + 1;
  }
  x = x / 2;
}
cout << L << endl << M << endl;
return 0;
}

📹 Видеоразбор подобного 20 задания ЕГЭ

✍ Решение:

В цикле:

Наличие операторов x mod 2 и x div 2 говорит о том, что эту задачу можно решать, представляя x в двоичной системе счисления.
В цикле есть счетчик M, который увеличивается на единицу и в конце программы будет соответствовать количеству итераций цикла. Таким образом, имеем 7 проходов цикла (в конце выводится M — по условию задания — число 7).
Условие if x mod 2 = 0 проверяет на четность младший разряд числа в двоичной системе:

например, если было x = 5₁₀ = 101₂, 
то if x mod 2 = 0 проверяет if 1 = 0

Если в младшем разряде стоит ноль (в двоичной системе число состоит только из чисел 1 и 0), то срабатывает счетчик L, который увеличивается на единицу.
В строке x := x div 2; отсекается младший разряд двоичного представления значения x, т.е.:

если было, например, x = 5₁₀ = 101₂, то стало x = 10₂

Таким образом, счетчик L подсчитывает количество нулей в двоичной записи числа. Так как в результате выводится L = 6, то в двоичной записи числа 6 нулей.
Так как цикл работает 7 раз и в каждую итерацию от числа в двоичной записи отсекается один разряд, то имеем 6 разрядов (цифр) в числе.
Итого, в двоичной записи 6 нулей и 1 единица. Для получения наименьшего x (по заданию) расположим цифры следующим образом:

1000000₂ = 64 + 0 + 0 + 0 + 0 + 0 + 0 = 64₁₀

Результат: 64

Источник

Е22.17. Решение задания №20 Досрочный вариант №1 ЕГЭ по информатике 2020

Решение задания №20 Досрочный вариант №1 ЕГЭ по информатике 2020 от ФИПИ. Информатика ЕГЭ 20 задание разбор. Как решать задание №20 ЕГЭ по информатике 2020 г.

Ниже на пяти языках программирования записан алгоритм. Получив на вход натуральное десятичное число x, этот алгоритм печатает два числа: L и M.

Укажите наибольшее число x, при вводе которого алгоритм выводит сначала 2, а потом 3.

Бейсик

Python

DIM X, L, M AS INTEGER

INPUT X

L = 0

M = 0

WHILE X > 0

M = M + 1

IF X MOD 2 <> 0 THEN

L = L + X MOD 8

END IF

X = X 8

WEND

PRINT L

PRINT M

x = int(input())

L = 0

M = 0

while x > 0:

M = M + 1

if x % 2 != 0:

L = L + x % 8

x = x // 8

print(L)

print(M)

Алгоритмический язык

Паскаль

алг

нач

цел x, L, M

ввод x

L := 0

M := 0

нц пока x > 0

M := M + 1

если mod(x, 2) <> 0

то

L := L + mod(x, 8)

все

x := div(x, 8)

кц

вывод L, нс, M

кон

var x, L, M: integer;

begin

readln(x);

L := 0;

M := 0;

while x > 0 do

begin

M := M + 1;

if x mod 2 <> 0 then

L := L + x mod 8;

x := x div 8

end;

writeln(L);

writeln(M)

end.

С++

#include <iostream>

using namespace std;

int main(){

int x, L, M;

cin >> x;

L = 0;

M = 0;

while (x > 0) {

M = M + 1;

if(x % 2 != 0) {

L = L + x % 8;

}

x = x / 8;

}

cout << L << endl << M << endl;

return 0;

}

Источник

Решение ГИА в форме ЕГЭ по информатике 20 задание из демоверсии 2020 года.

Задание на анализ алгоритма, содержащего цикл и ветвление.

ЕГЭ по информатике 2020 задание 20 1

ЕГЭ по информатике 2020 задание 20 2

var
  x, L, M: integer;
begin
  readln(x);
  L := 0;
  M := 0;
  while x > 0 do
  begin
    M := M + 1;
    if x mod 2 = 0 then
      L := L + 1;
    x := x div 2;
  end;
  writeln(L);
  writeln(M);
end.

Рассмотрим алгоритм:

В цикле:

Наличие операторов x mod 2 и x div 2 говорит о том, что эту задачу можно решать, представляя x в двоичной системе счисления.

В цикле есть счетчик M, который увеличивается на единицу и в конце программы будет соответствовать количеству итераций цикла. Таким образом, имеем 7 проходов цикла (в конце выводится M — по условию задания — число 7).

Условие if x mod 2 = 0 проверяет на четность младший разряд числа в двоичной системе:

например, если было x = 5₁₀ = 101₂, 
то if x mod 2 = 0 проверяет if 1 = 0

Если в младшем разряде стоит ноль (в двоичной системе число состоит только из чисел 1 и 0), то срабатывает счетчик L, который увеличивается на единицу.

В строке x := x div 2; отсекается младший разряд двоичного представления значения x, т.е.:

если было, например, x = 5₁₀ = 101₂, то стало x = 10₂

Таким образом, счетчик L подсчитывает количество нулей в двоичной записи числа. Так как в результате выводится L = 6, то в двоичной записи числа 6 нулей.

Так как цикл работает 7 раз и в каждую итерацию от числа в двоичной записи отсекается один разряд, то имеем 6 разрядов (цифр) в числе.

Итого, в двоичной записи 6 нулей и 1 единица. Для получения наименьшего x (по заданию) расположим цифры следующим образом:

1000000₂ = 64 + 0 + 0 + 0 + 0 + 0 + 0 = 64₁₀

Ответ: 64

Источник

Условие задачи

Ниже на пяти языках программирования записан алгоритм. Получив на вход натуральное десятичное число x, этот алгоритм печатает два числа: L и M. Укажите наибольшее число x, при вводе которого алгоритм выводит сначала 2, а потом 3.

Бейсик	Python
DIM X, L, M AS INTEGER INPUT X L = 0 M = 0 WHILE X > 0 M = M + 1 IF X MOD 2 <> 0 THEN L = L + X MOD 8 END IF X = X 8 WEND PRINT L PRINT M	x = int(input()) L = 0 M = 0 while x > 0: M = M + 1 if x % 2 != 0: L = L + x % 8 x = x // 8 print(L) print(M)
Алгоритмический язык	Паскаль
алг нач цел x, L, M ввод x L := 0 M := 0 нц пока x > 0 M := M + 1 если mod(x, 2) <> 0 то L := L + mod(x, 8) все x := div(x, 8) кц вывод L, нс, M кон	var x, L, M: integer; begin readln(x); L := 0; M := 0; while x > 0 do begin M := M + 1; if x mod 2 <> 0 then L := L + x mod 8; x := x div 8 end; writeln(L); writeln(M) end.
С++
#include <iostream> using namespace std; int main(){ int x, L, M; cin >> x; L = 0; M = 0; while (x > 0) { M = M + 1; if(x % 2 != 0) { L = L + x % 8; } x = x / 8; } cout << L << endl << M << endl; return 0; }

Решение

L = 2, M = 3
M – это количество цифр в 8-ричной записи числа, а L – это сумма его нечетных цифр.
Наибольшее число в 8-ричной системе, содержащее 3 цифры с суммой нечётных цифр = 2, это

Ответ

393.

Благодарим за то, что пользуйтесь нашими публикациями.
Информация на странице «Решение. Задание 20. Досрочный ЕГЭ 2020 года, Информатика» подготовлена нашими редакторами специально, чтобы помочь вам в освоении предмета и подготовке к экзаменам.
Чтобы успешно сдать нужные и поступить в высшее учебное заведение или техникум нужно использовать все инструменты: учеба, контрольные, олимпиады, онлайн-лекции, видеоуроки, сборники заданий.
Также вы можете воспользоваться другими материалами из разделов нашего сайта.

Публикация обновлена:
10.03.2023

Источник

Статьи

Среднее общее образование

Информатика

Предлагаем вашему вниманию разбор задания №20 ЕГЭ 2019 года по информатике и ИКТ. Этот материал содержит пояснения и подробный алгоритм решения, а также рекомендации по использованию справочников и пособий, которые могут понадобиться при подготовке к ЕГЭ.

26 марта 2019

ЕГЭ-2020. Информатика. Тематические тренировочные задания

Пособие содержит задания, максимально приближенные к реальным, используемым на ЕГЭ, но
распределенные по темам в порядке их изучения в 10-11-х классах старшей школы. Работая с книгой, можно
последовательно отработать каждую тему, устранить пробелы в знаниях, а также систематизировать изучаемый
материал. Такая структура книги поможет эффективнее подготовиться к ЕГЭ.

Купить

Демоверсия КИМ ЕГЭ-2019 по информатике не претерпела никаких изменений по своей структуре
по сравнению с 2018 годом. Это значимо упрощает работу педагога и, конечно, уже выстроенный
(хочется на это рассчитывать) план подготовки к экзамену обучающегося.

Мы рассмотрим решение предлагаемого проекта (на момент написания статьи – пока еще проекта) КИМ
ЕГЭ по информатике.

Часть 1

Ответами к заданиям 1–23 являются число, последовательность букв или цифр, которые следует записать
в БЛАНК ОТВЕТОВ № 1 справа от номера соответствующего задания, начиная с первой
клеточки, без пробелов, запятых и других дополнительных символов. Каждый символ пишите в отдельной
клеточке в соответствии с приведёнными в бланке образцами.

Задание 20

Ниже на пяти языках программирования записан алгоритм. Получив на вход натуральное десятичное число x, этот
алгоритм печатает два числа: L и M. Укажите наибольшее число x, при вводе которого алгоритм печатает сначала 21,
а потом 3.

Ответ: ___________________________.

Решение

Немного анализа кода:

Мы должны вывести значения переменных L и M. Переменная M (это заметно, если изучить код) указывает на число
итераций цикла, т.е. тело цикла должно выполниться ровно три раза.
Значение числа L, которое должно быть выведено первым, произведение, равное 21. Получить в произведении 21
можно из 7 и 3. Заметим также, что произведение возможно только при нечетном значении переменной x
в текущей итерации.
Оператор условия указывает на то, что один раз из трех значение переменной будет четным. В оставшиеся два
раза при нечетном значении переменной x мы получаем остаток от деления x на 8, который будет
равным один раз 3, а другой раз 7.
Значение переменной x уменьшается три раза в 8 раз операцией целочисленного деления.

Соединив все сказанное ранее, получаем два варианта:

x1 = (7 × 8 + ?) × 8 + 3 и x2 = (3 × 8 + ?) × 8 + 7

Вместо знака вопроса нам необходимо подобрать значение, которое будет не больше 8 и будет четным. Не забудем еще
про условие в задании – «наибольшее x». Большее четное, не превосходящее 8, – 6. А из x1 и x2, очевидно, что
первое больше. Вычислив, получим x=499.

Ответ: 499.

#ADVERTISING_INSERT#

Источник

Канал видеоролика: Подготовка к ЕГЭ

Смотреть видео:

Свежая информация для ЕГЭ и ОГЭ по Информатике (листай):

С этим видео ученики смотрят следующие ролики:

#22. Разбор 27х. Досрочный 2020, вар.1. ЕГЭ Информатика 2020

Подготовка к ЕГЭ

Разбор 1 задания демоверсия егэ по информатике 2020 : Сколько существует x, для которых выполняется

Светлана Майер

Разбор 2 задания демоверсия егэ по информатике 2020 ФИПИ : Миша заполнял таблицу истинности функции

Светлана Майер

Разбор задания 15.1 ДЕМО ОГЭ информатика 2020

Сдам ЕГЭ сам

Облегчи жизнь другим ученикам — поделись! (плюс тебе в карму):

15.04.2020

Комментарии

RSS

Написать комментарий

Нет комментариев. Ваш будет первым!

Ваше имя:

Загрузка…

Источник

Продолжаем решать задачи на теорию игр. Сегодня у нас разбор 20 задания из ЕГЭ по информатике 2021.

Задача (Одна куча)

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 30 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

Игра завершается в тот момент, когда количество камней в куче становится не менее 65. Победителем считается игрок, сделавший последний ход, т. е. первым получивший кучу, в которой будет 65 или больше камней. В начальный момент в куче было S камней 1 ≤ S ≤ 64.

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

— Петя не может выиграть за один ход;

— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.

Решение:

Ⅰ. Ход Пети.

S₀ — первоначальное количество камней в куче.

Т.к. Петя не может выиграть на своём своём первом ходе, то найдём значения S₀, при которых это возможно.

Распишем все варианты для Петиного первого хода.

+1	*2
S₀+1 < 65 S₀ < 64	2*S₀ < 65 S₀ < 33 (Округляем в большую сторону)

Все случаи должны быть удовлетворены, поэтому наш ответ должен быть меньше 33.

S₀ < 33

ⅠⅠ. Ход Вани.

Рассмотрим все два случая:

1. S₀+1 (Петя сделал +1 к кучке)

Ваня ни при каких обстоятельствах не должен выиграть на своём первом ходе. Найдём при каких значениях S₀ это будет выполняться для этой ветки.

+1	*2
S₀ + 2 < 65 S₀ < 63	2S₀ + 2 < 65 2S₀ < 63 S₀ < 32 (Округляем в большую сторону)

Для случая, когда Петя сделал +1 к кучке на первом своём ходу получается ограничение:

S₀ < 32

Рассмотрим, при каких значениях S₀ Петя на втором своём ходе может выиграть в данной ситуации.

a) Ваня оставил кучку: S₀+1+1 = S₀+2

+1	*2
S₀ + 3 ≥ 65 S₀ ≥ 62	2S₀ + 4 ≥ 65 2S₀ ≥ 61 S₀ ≥ 31 (Округляем в большую сторону)

С учётом всех ограничений получили значение S₀ = 31, при котором Петя может выиграть на втором своём ходе.

б) Ваня оставил кучку: 2*(S₀+1) = 2*S₀ + 2

+1	*2
2S₀ + 3 ≥ 65 2 S₀ ≥ 62 S₀ ≥ 31	4S₀ + 4 ≥ 65 4S₀ ≥ 61 S₀ ≥ 16 (Округляем в большую сторону)

Проанализируем два варианта a) и б) и понимаем, что в ответ пойдёт S₀ = 31. При таком начальном количестве камней у Вани не будет возможности «испортить игру» и в случае а), и в случае б).

2. 2*S₀ (Петя удвоил количество камней в куче.)

Найдём ограничения, при которых Ваня не выиграет при любых условиях на своём первом ходе.

+1	*2
2S₀ + 1 < 65 2S₀ < 64 S₀ < 32	4*S₀ < 65 S₀ < 17 (Округляем в большую сторону)

Значит, при этом первом ходе Пети, S₀ должно быть меньше 17.

S₀ < 17

Узнаем, при каких значениях S₀ Петя на втором своём ходе может выиграть в данной ситуации.

a) Ваня оставил 2*S₀+1.

+1	*2
2S₀ + 2 ≥ 65 2S₀ ≥ 63 S₀ ≥ 32 (Округляем в большую сторону)	4S₀ + 2 ≥ 65 4S₀ ≥ 63 S₀ ≥ 16 (Округляем в большую сторону)

С учётом ограничения S₀ < 17 получаем значение S₀ = 16.

б) Ваня оставил 2*2*S₀ = 4*S₀.

+1	*2
4S₀ + 1 ≥ 65 4S₀ ≥ 64 S₀ ≥ 16	8*S₀ ≥ 65 S₀ ≥ 9 (Округляем в большую сторону)

Объединив a) и б) для второго случая (когда первый ход Пети был 2*S₀), получаем значение S₀ = 16. Мы проверяли пункт б), чтобы проверить, нет ли возможности у Вани «испортить» игру.

В задаче просили найти 2 значения для переменной S, при которых будут выполняться условия задачи. Мы нашли два значения. На этом можно завершить решение и записать ответ.

Ответ: 1631

Решим задачу из Демонстрационного варианта ЕГЭ по информатике 2021.

Задача (Демонстрационный вариант ЕГЭ по информатике 2021)

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 5 камней; такую позицию в игре будем обозначать (10, 5). Тогда за один ход можно получить любую из четырёх позиций: (11, 5), (20, 5), (10, 6), (10, 10). Для того чтобы делать ходы,
у каждого игрока есть неограниченное количество камней.

Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 77. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 77 или больше камней.

В начальный момент в первой куче было семь камней, во второй куче –
S камней; 1 ≤ S ≤ 69.

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т.е. не являющиеся выигрышными независимо от игры противника.

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

− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как
будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания.

Решение:

Обозначим первую кучу за a, вторую кучу за b.

Ⅰ. Ход Пети.

S₀ — первоначальное количество камней во второй куче.

a=7, b=S₀.

Т.к. Петя не может выиграть на своём своём первом ходе, то найдём значения S₀, при которых это возможно.

Петя может сделать всего 4 действия. Распишем сумму двух кучек для 4-х случаев. Эти суммы должны быть меньше 77.

a+1+b	a + b+1	*2a** + b	a + *2b**
S₀ + 8 < 77 S₀ < 69	S₀ + 8 < 77 S₀ < 69	S₀ + 14 < 77 S₀ < 63	2S₀ + 7 < 77 2S₀ < 70 S₀ < 35

Все случаи должны быть удовлетворены, поэтому наш ответ должен быть меньше 35.

S₀ < 35

ⅠⅠ. Ход Вани.

Рассмотрим случай, когда Петя оставил следующие кучки:

1. a=8, b=S₀ (Петя сделал +1 к первой кучке)

a+1+b	a + b+1	*2a** + b	a + *2b**
S₀ + 9 < 77 S₀ < 68	S₀ + 9 < 77 S₀ < 68	S₀ + 16 < 77 S₀ < 61	2S₀ + 8 < 77 2S₀ < 69 S₀ < 35 (Округляем в большую сторону)

Получается, что для случая, когда Петя сделал +1 к первой кучке, нам подходят значения для S₀ < 35. В этом случае есть возможность Ване НЕ выиграть на своём ходе. Это ограничение совпадает с главным ограничением, которое мы получили на первом ходе Пети.

S₀ < 35

Рассмотрим, при каких значениях S₀ Петя на втором своём ходе может выиграть в данной ситуации.

a) Ваня оставил a=9 (8+1), b=S₀.

a+1+b	a + b+1	*2a** + b	a + *2b**
S₀ + 10 ≥ 77 S₀ ≥ 67	S₀ + 10 ≥ 77 S₀ ≥ 67	S₀ + 18 ≥ 77 S₀ ≥ 59	2S₀ + 9 ≥ 77 2S₀ ≥ 68 S₀ ≥ 34

С учётом всех ограничений получили значение S₀ = 34, при котором Петя будет выигрывать на втором своём ходе. Это значение наибольшее в допустимом диапазоне. Меньше значение теперь мы получить не можем (при данном первом ходе Пети), потому что у Вани есть возможность всегда «свернуть» в пункт а), и здесь значения меньшие, чем 34 не проходят.

Рассмотрим остальные ходы Вани. Если у него будет возможность пойти так, что Петя на втором ходе не сможет выиграть, значит, он так всегда сможет ходить, и наш ответ S₀ = 34 нельзя будет засчитать.

б) Ваня оставил a=8, b=S₀+1.

a+1+b	a + b+1	*2a** + b	a + *2b**
S₀ + 10 ≥ 77 S₀ ≥ 67	S₀ + 10 ≥ 77 S₀ ≥ 67	S₀ + 17 ≥ 77 S₀ ≥ 60	2S₀ + 10 ≥ 77 2S₀ ≥ 67 S₀ ≥ 34 (Округляем в большую сторону)

В пункте б) есть решение.

в) Ваня оставил a=16, b=S₀.

a+1+b	a + b+1	*2a** + b	a + *2b**
S₀ + 17 ≥ 77 S₀ ≥ 60	S₀ + 17 ≥ 77 S₀ ≥ 60	S₀ + 32 ≥ 77 S₀ ≥ 45	2S₀ + 16 ≥ 77 2S₀ ≥ 61 S₀ ≥ 31 (Округляем в большую сторону)

В пункте в) есть решения.

г) Ваня оставил a=8, b=2*S₀.

a+1+b	a + b+1	*2a** + b	a + *2b**
2S₀ + 9 ≥ 77 2S₀ ≥ 68 S₀ ≥ 34	—	—	—

Пункт г) тоже имеет решение. Как только нашли за Петю решение, можно прекратить рассматривать оставшиеся ходы у Пети на втором ходе, потому что мы нашли уже максимальное значение S₀ = 34 из диапазона S₀ < 35, и в пунктах б), в), г) нам важно убедиться, что решения просто есть.

Мы должны выбрать из всех четырёх пунктов (а), б), в), г)) самое больше число. Это будет S₀ = 34. Именно это значение удовлетворяет всем четырём пунктам одновременно. Тогда у Вани не будет возможности сходить так, что Петя на своём втором ходе не сможет выиграть.

Получается, что значение S₀ = 34 пойдёт в ответ.

2. a=7, b=S₀+1 (Петя сделал +1 ко второй кучке)

Найдём ограничения, при которых Ваня не выиграет при любых условиях на своём первом ходе.

a+1+b	a + b+1	*2a** + b	a + *2b**
S₀ + 9 < 77 S₀ < 68	S₀ + 9 < 77 S₀ < 68	S₀ + 15 < 77 S₀ < 62	2S₀ + 9 < 77 2S₀ < 68 S₀ < 34

Значит, при этом первом ходе Пети, S₀ должно быть меньше 34.

S₀ < 34

Узнаем, при каких значениях S₀ Петя на втором своём ходе может выиграть в данной ситуации.

a) Ваня оставил a=8 (7+1), b=S₀+1.

a+1+b	a + b+1	*2a** + b	a + *2b**
S₀ + 10 ≥ 77 S₀ ≥ 67	S₀ + 10 ≥ 77 S₀ ≥ 67	S₀ + 17 ≥ 77 S₀ ≥ 60	2S₀ + 10 ≥ 77 2S₀ ≥ 67 S₀ ≥ 34 (Округляем в большую сторону)

Видим, что у Вани есть возможность «свернуть» на путь a=8 (7+1), b=S₀+1, и тем самым, не оставить шансов Пети выиграть. (Ни одно неравенство не пройдёт ограничение S₀ < 34).

Значит, вариант a=7, b=S₀+1 на первом Петином ходу не принёс результатов.

3. a=14, b=S₀ (Петя увеличил первую кучку в 2 раза.)

Найдём ограничения, при которых Ваня не выиграет при любых условиях на своём первом ходе.

a+1+b	a + b+1	*2a** + b	a + *2b**
S₀ + 15 < 77 S₀ < 62	S₀ + 15 < 77 S₀ < 62	S₀ + 28 < 77 S₀ < 49	2S₀ + 14 < 77 2S₀ < 63 S₀ < 32 (Округляем в большую сторону)

Значит, при этом первом ходе Пети, S₀ должно быть меньше 32.

S₀ < 32

Узнаем, при каких значениях S₀ Петя на втором своём ходе может выиграть в данной ситуации.

a) Ваня оставил a=15 (14+1), b=S₀.

a+1+b	a + b+1	*2a** + b	a + *2b**
S₀ + 16 ≥ 77 S₀ ≥ 61	S₀ + 16 ≥ 77 S₀ ≥ 61	S₀ + 30 ≥ 77 S₀ ≥ 47	2S₀ + 15 ≥ 77 2S₀ ≥ 62 S₀ ≥ 31

С учётом ограничения S₀ < 32 получаем значение S₀ = 31. Получили наибольшее значение в допустимом диапазоне. Значит, меньше чем 31, в данной ветке значение быть не может.

Убедимся, что при остальных ходах Вани, Петя сможет выиграть на своём втором ходе.

б) Ваня оставил a=14, b=S₀+1.

a+1+b	a + b+1	*2a** + b	a + *2b**
S₀ + 16 ≥ 77 S₀ ≥ 61	S₀ + 16 ≥ 77 S₀ ≥ 61	S₀ + 29 ≥ 77 S₀ ≥ 48	2S₀ + 16 ≥ 77 2S₀ ≥ 61 S₀ ≥ 31 (Округляем в большую сторону)

Пункт б) имеет решение.

в) Ваня оставил a=28, b=S₀.

a+1+b	a + b+1	*2a** + b	a + *2b**
S₀ + 29 ≥ 77 S₀ ≥ 48	S₀ + 29 ≥ 77 S₀ ≥ 48	S₀ + 56 ≥ 77 S₀ ≥ 21	—

Пункт в) имеет решения.

г) Ваня оставил a=14, b=2*S₀.

a+1+b	a + b+1	*2a** + b	a + *2b**
2S₀ + 15 ≥ 77 2S₀ ≥ 62 S₀ ≥ 31	—	—	—

В пункте г) есть решение.

Таким образом, мы нашли наибольшее решение S₀ = 31 при ограничении S₀ < 32. Оно подходит для всех четырёх пунктов а), б) в), г).

Ответ: 3134

Посмотрим ещё одну задачу 20 Задания из примерных вариантов ЕГЭ по информатике 2021.

Задача (Закрепление)

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может

добавить в одну из куч один камень или
увеличить количество камней в куче в два раза.

Например, пусть в одной куче 6 камней, а в другой 9 камней; такую позицию мы будем обозначать (6, 9). За один ход из позиции (6, 9) можно получить любую из четырёх позиций: (7, 9), (12, 9), (6, 10), (6, 18). Чтобы делать ходы, у каждого игрока есть неограниченное количество камней.

Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 74. Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в кучах будет 74 или больше камней.

В начальный момент в первой куче было 12 камней, во второй куче — S камней, 1 ≤ S ≤ 61.

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

— Петя не может выиграть за один ход;

— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.

Решение:

Обозначим первую кучу за a, вторую кучу за b.

Ⅰ. Ход Пети.

S₀ — первоначальное количество камней во второй куче.

a=12, b=S₀.

Т.к. Петя не может выиграть на своём своём первом ходе, то найдём значения S₀, при которых это возможно.

Петя может сделать всего 4 действия. Распишем сумму двух кучек для 4-х случаев. Эти суммы должны быть меньше 74.

a+1+b	a + b+1	*2a** + b	a + *2b**
S₀ + 13 < 74 S₀ < 61	S₀ + 13 < 74 S₀ < 61	S₀ + 24 < 74 S₀ < 50	2S₀ + 12 < 74 2S₀ < 62 S₀ < 31

Все случаи должны быть удовлетворены, поэтому наш ответ должен быть меньше 31.

S₀ < 31

ⅠⅠ. Ход Вани.

Рассмотрим случай, когда Петя оставил следующие кучки:

1. a=13, b=S₀ (Петя сделал +1 к первой кучке)

a+1+b	a + b+1	*2a** + b	a + *2b**
S₀ + 14 < 74 S₀ < 60	S₀ + 14 < 74 S₀ < 60	S₀ + 26 < 74 S₀ < 48	2S₀ + 13 < 74 2S₀ < 61 S₀ < 31 (Округляем в большую сторону)

Получается, что для случая, когда Петя сделал +1 к первой кучке, нам подходят значения для S₀ < 31. В этом случае есть возможность Ване НЕ выиграть на первом своём ходе. Это ограничение совпадает с главным ограничением, которое мы получили на первом ходе Пети.

S₀ < 31

Рассмотрим, при каких значениях S₀ Петя на втором своём ходе может выиграть в данной ситуации.

a) Ваня оставил a=14 (13+1), b=S₀.

a+1+b	a + b+1	*2a** + b	a + *2b**
S₀ + 15 ≥ 74 S₀ ≥ 59	S₀ + 15 ≥ 74 S₀ ≥ 59	S₀ + 28 ≥ 74 S₀ ≥ 46	2S₀ + 14 ≥ 74 2S₀ ≥ 60 S₀ ≥ 30

С учётом всех ограничений получили значение S₀ = 30, при котором Петя будет выигрывать на втором своём ходе. Это максимальное значение, для данного ограничения S₀ < 32. Даже, если мы найдём меньшее число при других ходах Вани в этой ветке, всё равно мы выберем значение 32. Но всё же нужно проверить остальные ходы Вани, вдруг у него будет возможность выводить нас на такую ситуацию, когда Петя не сможет выиграть на своём втором ходе.

б) Ваня оставил a=13, b=S₀+1.

a+1+b	a + b+1	*2a** + b	a + *2b**
S₀ + 15 ≥ 74 S₀ ≥ 59	S₀ + 15 ≥ 74 S₀ ≥ 59	S₀ + 27 ≥ 74 S₀ ≥ 47	2S₀ + 15 ≥ 74 2S₀ ≥ 59 S₀ ≥ 30 (Округляем в большую сторону)

Пункт б) имеет решения.

в) Ваня оставил a=26, b=S₀.

a+1+b	a + b+1	*2a** + b	a + *2b**
S₀ + 27 ≥ 74 S₀ ≥ 47	S₀ + 27 ≥ 74 S₀ ≥ 47	S₀ + 52 ≥ 74 S₀ ≥ 22	—

Пункт в) имеет решения.

г) Ваня оставил a=13, b=2*S₀.

a+1+b	a + b+1	*2a** + b	a + *2b**
2S₀ + 14 ≥ 74 2S₀ ≥ 60 S₀ ≥ 30	—	—	—

Пункт г) имеет решение.

Таким образом, значение S₀ = 30 удовлетворяет всем четырём пунктам, и у Вани нет возможности «испортить праздник» Пети.

Один ответ есть.

2. a=12, b=S₀+1 (Петя сделал +1 ко второй кучке)

Найдём ограничения, при которых Ваня не выиграет при любых условиях на своём первом ходе.

a+1+b	a + b+1	*2a** + b	a + *2b**
S₀ + 14 < 74 S₀ < 60	S₀ + 14 < 74 S₀ < 60	S₀ + 25 < 74 S₀ < 49	2S₀ + 14 < 74 2S₀ < 60 S₀ < 30

Значит, при этом первом ходе Пети, S₀ должно быть меньше 30.

S₀ < 30

Узнаем, при каких значениях S₀ Петя на втором своём ходе может выиграть в данной ситуации.

a) Ваня оставил a=13 (12+1), b=S₀+1.

a+1+b	a + b+1	*2a** + b	a + *2b**
S₀ + 15 ≥ 74 S₀ ≥ 59	S₀ + 15 ≥ 74 S₀ ≥ 59	S₀ + 27 ≥ 74 S₀ ≥ 47	2S₀ + 15 ≥ 74 2S₀ ≥ 67 S₀ ≥ 30 (Округляем в большую сторону)

Видим, что у Вани есть возможность «свернуть» на путь a=13 (12+1), b=S₀+1, и тем самым, не оставить шансов Пети выиграть. (Ни одно неравенство не пройдёт ограничение S₀ < 30).

Значит, вариант a=12, b=S₀+1 на первом Петином ходу не принёс результатов.

3. a=24, b=S₀ (Петя увеличил первую кучку в 2 раза.)

Найдём ограничения, при которых Ваня не выиграет при любых условиях на своём первом ходе.

a+1+b	a + b+1	*2a** + b	a + *2b**
S₀ + 25 < 74 S₀ < 49	S₀ + 25 < 74 S₀ < 49	S₀ + 48 < 74 S₀ < 26	2S₀ + 24 < 74 2S₀ < 50 S₀ < 25

Значит, при этом первом ходе Пети, S₀ должно быть меньше 25.

S₀ < 25

Узнаем, при каких значениях S₀ Петя на втором своём ходе может выиграть в данной ситуации.

a) Ваня оставил a=25 (24+1), b=S₀.

a+1+b	a + b+1	*2a** + b	a + *2b**
S₀ + 26 ≥ 74 S₀ ≥ 48	S₀ + 26 ≥ 74 S₀ ≥ 48	S₀ + 50 ≥ 74 S₀ ≥ 24	2S₀ + 27 ≥ 74 2S₀ ≥ 47 S₀ ≥ 24 (Округляем в большую сторону)

С учётом ограничения S₀ < 25 получаем значение S₀ = 24. Максимальное значение при допустимом диапазоне. Значит, меньше чем 24, значение при данном первом ходе Пети быть не может, иначе оно не будет проходить в пункте а).

Проверим остальные ходы Вани.

б) Ваня оставил a=24, b=S₀+1.

a+1+b	a + b+1	*2a** + b	a + *2b**
S₀ + 26 ≥ 74 S₀ ≥ 48	S₀ + 26 ≥ 74 S₀ ≥ 48	S₀ + 49 ≥ 74 S₀ ≥ 25	2S₀ + 26 ≥ 74 2S₀ ≥ 48 S₀ ≥ 24

Пункт б) имеет решение.

в) Ваня оставил a=48, b=S₀.

a+1+b	a + b+1	*2a** + b	a + *2b**
S₀ + 49 ≥ 74 S₀ ≥ 25	S₀ + 49 ≥ 74 S₀ ≥ 25	S₀ + 96 ≥ 74 S₀ ≥ 1	—

Пункт в) имеет решения.

г) Ваня оставил a=24, b=2*S₀.

a+1+b	a + b+1	*2a** + b	a + *2b**
2S₀ + 25 ≥ 74 2S₀ ≥ 49 S₀ ≥ 25	2S₀ + 25 ≥ 74 2S₀ ≥ 49 S₀ ≥ 25	2S₀ + 48 ≥ 74 2S₀ ≥ 26 S₀ ≥ 13	—

Пункт г) имеет решения.

Ваня не сможет сделать такой ход, при котором Петя не сможет выиграть на втором ходе.

Выбираем такое значение S₀ = 24, которое подходит под все пункты а), б), в), г).

Пишем ответ из двух значений 24 и 30.

Ответ: 2430

На этом всё. Удачи на экзамене по информатике 2021!

Источник