ЕГЭ19_21_27

1. Информатика

ЕГЭ-19, 20, 21
Тема: Игровые стратегии

2.

Проверяется:
• умение анализировать алгоритм логической игры;
• умение найти выигрышную стратегию игры;
• умение построить дерево игры по заданному
алгоритму и найти выигрышную стратегию.
2

3. Теория

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

4. Вывод:

общая стратегия игры
состоит в том, чтобы
своим ходом создать
проигрышную позицию
для соперника
4

5. Варианты задач:

• одна куча;
• две кучи;
• три кучи;
• уменьшение количества камней;
• увеличение количества камней
5

6. Одна куча - увеличение

ЕГЭ-19 Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча
камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может:
1. Добавить в кучу один камень или
2. Добавить в кучу три камня или
3. Увеличить количество камней в куче в четыре раза.
Например, имея кучу из 20 камней, за одни ход можно получить кучу из 21, 23 или 80
камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее
78. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу,
в которой будет 78 или больше камней. В начальный момент в куче было S камней: 1 ≤ S ≤
77.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при
любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен
сделать в любой ситуации, которая ему может встретится при различной игре противника. В
описание выигрышной стратегии не следует включать ходы играющего по этой стратегии
игрока, не являющиеся для него безусловно выигрышными, т.е. не являющиеся
выигрышными независимо от игры противника.
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети.
Укажите минимальное значение S, когда такая ситуация возможна.
6

7. Рассуждение

7

8. Рассуждение

8

9. Программа на Python

9

10. Программа на Python

# создаем функцию с условиями игры
def f(s, p):
# s - начальное количество камней в куче, p - номер хода
# победа у Вани, следовательно p=2 (второй ход игры) и s=78
if s >= 78 and p == 2:
return True # можно поставить просто 1
if s < 78 and p == 2: # если на втором (p=2) ходе мы не набрали 78, это ложь
return False # можно поставить просто 0
if s >= 78 and p < 2: # если набрали 78 до второго (p=2) хода, это ложь
return False # можно поставить просто 0
# прописываем правила игры для ее продолжения
# s+1 - добавить один камень
# s+3 - добавить три камня
# 4*s - увеличить количество камней в 4 раза
# p+1 - номер ходо ВСЕГДА увеличивать на 1
return f(s+1, p+1) or f(s+3, p+1) or f(4*s, p+1)
for s in range(1, 77):
if f(s, 0):
print('19: ', s)
break
10

11. Программа на Python

# создаем функцию с условиями игры
def f(s, p):
# s - начальное количество камней в куче, p - номер хода
# победа у Вани, следовательно p=2 (второй ход игры) и s=78
if s >= 78 and p == 2:
return True # можно поставить просто 1
if s < 78 and p == 2: # если на втором (p=2) ходе мы не набрали 78, это ложь
return False # можно поставить просто 0
if s >= 78 and p < 2: # если набрали 78 до второго (p=2) хода, это ложь
return False # можно поставить просто 0
# прописываем правила игры для ее продолжения
# s+1 - добавить один камень
# s+3 - добавить три камня
# 4*s - увеличить количество камней в 4 раза
# p+1 - номер ходо ВСЕГДА увеличивать на 1
return f(s+1, p+1) or f(s+3, p+1) or f(4*s, p+1)
for s in range(1, 77):
if f(s, 0):
print('19: ', s)
break
11

12. Программа на Python

# создаем функцию с условиями игры
def f(s, p):
# s - начальное количество камней в куче, p - номер хода
# победа у Вани, следовательно p=2 (второй ход игры) и s=78
if s >= 78 and p == 2:
return True # можно поставить просто 1
if s < 78 and p == 2: # если на втором (p=2) ходе мы не набрали 78, это ложь
return False # можно поставить просто 0
if s >= 78 and p < 2: # если набрали 78 до второго (p=2) хода, это ложь
return False # можно поставить просто 0
# прописываем правила игры для ее продолжения
# s+1 - добавить один камень
# s+3 - добавить три камня
# 4*s - увеличить количество камней в 4 раза
# p+1 - номер ходо ВСЕГДА увеличивать на 1
return f(s+1, p+1) or f(s+3, p+1) or f(4*s, p+1)
for s in range(1, 77):
if f(s, 0):
print('19: ', s)
break
12

13. Программа на Python

# создаем функцию с условиями игры
def f(s, p):
# s - начальное количество камней в куче, p - номер хода
# победа у Вани, следовательно p=2 (второй ход игры) и s=78
if s >= 78 and p == 2:
return True # можно поставить просто 1
if s < 78 and p == 2: # если на втором (p=2) ходе мы не набрали 78, это ложь
return False # можно поставить просто 0
if s >= 78 and p < 2: # если набрали 78 до второго (p=2) хода, это ложь
return False # можно поставить просто 0
# прописываем правила игры для ее продолжения
# s+1 - добавить один камень
# s+3 - добавить три камня
# 4*s - увеличить количество камней в 4 раза
# p+1 - номер ходо ВСЕГДА увеличивать на 1
return f(s+1, p+1) or f(s+3, p+1) or f(4*s, p+1)
for s in range(1, 77):
if f(s, 0):
print('19: ', s)
break
13

14. Программа на Python

# создаем функцию с условиями игры
def f(s, p):
# s - начальное количество камней в куче, p - номер хода
# победа у Вани, следовательно p=2 (второй ход игры) и s=78
if s >= 78 and p == 2:
return True # можно поставить просто 1
if s < 78 and p == 2: # если на втором (p=2) ходе мы не набрали 78, это ложь
return False # можно поставить просто 0
if s >= 78 and p < 2: # если набрали 78 до второго (p=2) хода, это ложь
return False # можно поставить просто 0
# прописываем правила игры для ее продолжения
# s+1 - добавить один камень
# s+3 - добавить три камня
# 4*s - увеличить количество камней в 4 раза
# p+1 - номер хода ВСЕГДА увеличивать на 1
return f(s+1, p+1) or f(s+3, p+1) or f(4*s, p+1)
for s in range(1, 77):
if f(s, 0):
print('19: ', s)
break
14

15. Программа на Python

# создаем функцию с условиями игры
def f(s, p):
# s - начальное количество камней в куче, p - номер хода
# победа у Вани, следовательно p=2 (второй ход игры) и s=78
if s >= 78 and p == 2:
return True # можно поставить просто 1
if s < 78 and p == 2: # если на втором (p=2) ходе мы не набрали 78, это ложь
return False # можно поставить просто 0
if s >= 78 and p < 2: # если набрали 78 до второго (p=2) хода, это ложь
return False # можно поставить просто 0
# прописываем правила игры для ее продолжения
# s+1 - добавить один камень
# s+3 - добавить три камня
# 4*s - увеличить количество камней в 4 раза
# p+1 - номер хода ВСЕГДА увеличивать на 1
return f(s+1, p+1) or f(s+3, p+1) or f(4*s, p+1)
for s in range(1, 77):
if f(s, 0):
print('19: ', s)
break
15

16. Программа на Python

# создаем функцию с условиями игры
def f(s, p):
# s - начальное количество камней в куче, p - номер хода
# победа у Вани, следовательно p=2 (второй ход игры) и s=78
if s >= 78 and p == 2:
return True # можно поставить просто 1
if s < 78 and p == 2: # если на втором (p=2) ходе мы не набрали 78, это ложь
return False # можно поставить просто 0
if s >= 78 and p < 2: # если набрали 78 до второго (p=2) хода, это ложь
return False # можно поставить просто 0
# прописываем правила игры для ее продолжения
# s+1 - добавить один камень
# s+3 - добавить три камня
# 4*s - увеличить количество камней в 4 раза
# p+1 - номер хода ВСЕГДА увеличивать на 1
return f(s+1, p+1) or f(s+3, p+1) or f(4*s, p+1)
for s in range(1, 77):
if f(s, 0):
print('19: ', s)
break
16

17. Программа на Python

# создаем функцию с условиями игры
def f(s, p):
# s - начальное количество камней в куче, p - номер хода
# победа у Вани, следовательно p=2 (второй ход игры) и s=78
if s >= 78 and p == 2:
return True # можно поставить просто 1
if s < 78 and p == 2: # если на втором (p=2) ходе мы не набрали 78, это ложь
return False # можно поставить просто 0
if s >= 78 and p < 2: # если набрали 78 до второго (p=2) хода, это ложь
return False # можно поставить просто 0
# прописываем правила игры для ее продолжения
# s+1 - добавить один камень
# s+3 - добавить три камня
# 4*s - увеличить количество камней в 4 раза
# p+1 - номер хода ВСЕГДА увеличивать на 1
return f(s+1, p+1) or f(s+3, p+1) or f(4*s, p+1)
for s in range(1, 78):
if f(s, 0):
print('19: ', s)
break
Ответ: 19: 5
17

18. ЕГЭ-20 - Python

Для игры, описанной в задании 19, найдите два таких
значения S, при которых у Пети есть выигрышная стратегия,
причем одновременно выполняются два условия:
• Петя не может выиграть за один ход;
• Петя может выиграть своим вторым ходом независимо от
того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке
возрастания.
18

19. Рассуждение

19

20. Рассуждение

Получили ДВА подходящих значения
16 и 18
5 и 4 использовать НЕЛЬЗЯ,
т.к. - 5 много, а 4 - мало
20

21. Копируем предыдущий код и переделываем

21

22. Копируем предыдущий код и переделываем

# создаем функцию с условиями игры
def f(s, p):
# s - начальное количество камней в куче, p - номер хода
# победа у Пети, следовательно p=3 (третий ход игры) и s=78
if s >= 78 and p == 3:
return True
# можно поставить просто 1
if s < 78 and p == 3:
return False
# можно поставить просто 0
if s >= 78 and p < 3:
return False
# если на третьем (p=3) ходе мы не набрали 78, это ложь
# если набрали 78 до третьего (p=3) хода, это ложь
# можно поставить просто 0
# прописываем правила игры для ее продолжения
# s+1 - добавить один камень
# s+3 - добавить три камня
# 4*s - увеличить количество камней в 4 раза
# p+1 - номер ходо ВСЕГДА увеличивать на 1
Ответ: 19: 5
# Ваня ходит как угодно, поэтому прописываем следующее условие
if p % 2 == 0:
return f(s+1, p+1) or f(s+3, p+1) or f(4*s, p+1)
else:
return f(s+1, p+1) and f(s+3, p+1) and f(4*s, p+1)
for s in range(1, 77):
if f(s, 0):
print('20: ', s)
22

23. Копируем предыдущий код и переделываем

# создаем функцию с условиями игры
def f(s, p):
# s - начальное количество камней в куче, p - номер хода
# победа у Пети, следовательно p=3 (третий ход игры) и s=78
if s >= 78 and p == 3:
return True
# можно поставить просто 1
if s < 78 and p == 3:
return False
# можно поставить просто 0
if s >= 78 and p < 3:
return False
# если на третьем (p=3) ходе мы не набрали 78, это ложь
# если набрали 78 до третьего (p=3) хода, это ложь
# можно поставить просто 0
# прописываем правила игры для ее продолжения
# s+1 - добавить один камень
# s+3 - добавить три камня
# 4*s - увеличить количество камней в 4 раза
# p+1 - номер хода ВСЕГДА увеличивать на 1
# Ваня ходит как угодно, поэтому прописываем следующее условие
if p % 2 == 0:
return f(s+1, p+1) or f(s+3, p+1) or f(4*s, p+1)
else:
return f(s+1, p+1) and f(s+3, p+1) and f(4*s, p+1)
for s in range(1, 77):
if f(s, 0):
print('20: ', s)
23

24. Копируем предыдущий код и переделываем

# создаем функцию с условиями игры
def f(s, p):
# s - начальное количество камней в куче, p - номер хода
# победа у Пети, следовательно p=3 (третий ход игры) и s=78
if s >= 78 and p == 3:
return True
# можно поставить просто 1
if s < 78 and p == 3:
return False
# можно поставить просто 0
if s >= 78 and p < 3:
return False
# если на третьем (p=3) ходе мы не набрали 78, это ложь
# если набрали 78 до третьего (p=3) хода, это ложь
# можно поставить просто 0
# прописываем правила игры для ее продолжения
# s+1 - добавить один камень
# s+3 - добавить три камня
# 4*s - увеличить количество камней в 4 раза
# p+1 - номер хода ВСЕГДА увеличивать на 1
# Ваня ходит как угодно, поэтому прописываем следующее условие
if p % 2 == 0:
return f(s+1, p+1) or f(s+3, p+1) or f(4*s, p+1)
else:
return f(s+1, p+1) and f(s+3, p+1) and f(4*s, p+1)
for s in range(1, 77):
if f(s, 0):
print('20: ', s)
24

25. Копируем предыдущий код и переделываем

# создаем функцию с условиями игры
def f(s, p):
# s - начальное количество камней в куче, p - номер хода
# победа у Пети, следовательно p=3 (третий ход игры) и s=78
if s >= 78 and p == 3:
return True
# можно поставить просто 1
if s < 78 and p == 3:
return False
# можно поставить просто 0
if s >= 78 and p < 3:
return False
# если на третьем (p=3) ходе мы не набрали 78, это ложь
# если набрали 78 до третьего (p=3) хода, это ложь
# можно поставить просто 0
# прописываем правила игры для ее продолжения
# s+1 - добавить один камень
# s+3 - добавить три камня
# 4*s - увеличить количество камней в 4 раза
# p+1 - номер хода ВСЕГДА увеличивать на 1
# Ваня ходит как угодно, поэтому прописываем следующее условие
if p % 2 == 0:
return f(s+1, p+1) or f(s+3, p+1) or f(4*s, p+1)
else:
return f(s+1, p+1) and f(s+3, p+1) and f(4*s, p+1)
for s in range(1, 78):
if f(s, 0):
print('20: ', s)
Ответ:
20: 16
20: 18
25

26. ЕГЭ-21 - Python

Для игры, описанной в задании 19, найдите минимальное
значение S, при котором одновременно выполняются два
условия:
• у Вани есть выигрышная стратегия, позволяющая ему
выиграть первым или вторым ходом при любой игре Пети;
• у Вани нет стратегии, которая позволит ему
гарантированно выиграть первым ходом.
26

27. Рассуждение

27

28. Рассуждение

28

29. Копируем предыдущий код и переделываем

29

30. Копируем предыдущий код и переделываем

# создаем функцию с условиями игры
def f(s, p):
# s - начальное количество камней в куче, p - номер хода
# победа у Вани, выигрыш СВОИМ первым или вторым ходом, следовательно, p=2 или p=4 и s=78
if s >= 78 and (p == 3 or p == 4):
return True
# можно поставить просто 1
#
у Вас нет стратегии, которая позволяет ему гарантированно выиграть первым или вторым ходом
#
поэтому оставляем p=4
if s < 78 and p == 4:
return False
# можно поставить просто 0
if s >= 78 and p < 4:
return False
# если набрали 78 до третьего (p=4) хода, это ложь
# можно поставить просто 0
# прописываем правила игры для ее продолжения
# s+1 - добавить один камень
# s+3 - добавить три камня
# 4*s - увеличить количество камней в 4 раза
# p+1 - номер хода ВСЕГДА увеличивать на 1
# Петя ходит как угодно, поэтому прописываем следующее условие
if p % 2 != 0: # если похзиция нечетная, у Пети нечетные позиции (p=1 или p=3), то or
return f(s+1, p+1) or f(s+3, p+1) or f(4*s, p+1)
else: #
инача and
return f(s+1, p+1) and f(s+3, p+1) and f(4*s, p+1)
for s in range(1, 77):
if f(s, 0):
print(‘21: ', s)
30

31. Копируем предыдущий код и переделываем

# создаем функцию с условиями игры
def f(s, p):
# s - начальное количество камней в куче, p - номер хода
# победа у Вани, выигрыш СВОИМ первым или вторым ходом, следовательно, p=2 или p=4 и s=78
if s >= 78 and (p == 2 or p == 4):
return True
# можно поставить просто 1
#
у Вани нет стратегии, которая позволяет ему гарантированно выиграть первым или вторым ходом
#
поэтому оставляем p=4
if s < 78 and p == 4:
return False
# можно поставить просто 0
if s >= 78 and p < 4:
return False
# если набрали 78 до третьего (p=4) хода, это ложь
# можно поставить просто 0
# прописываем правила игры для ее продолжения
# s+1 - добавить один камень
# s+3 - добавить три камня
# 4*s - увеличить количество камней в 4 раза
# p+1 - номер хода ВСЕГДА увеличивать на 1
# Петя ходит как угодно, поэтому прописываем следующее условие
if p % 2 != 0: # если похзиция нечетная, у Пети нечетные позиции (p=1 или p=3), то or
return f(s+1, p+1) or f(s+3, p+1) or f(4*s, p+1)
else: #
инача and
return f(s+1, p+1) and f(s+3, p+1) and f(4*s, p+1)
for s in range(1, 77):
if f(s, 0):
print(‘21: ', s)
31

32. Копируем предыдущий код и переделываем

# создаем функцию с условиями игры
def f(s, p):
# s - начальное количество камней в куче, p - номер хода
# победа у Вани, выигрыш СВОИМ первым или вторым ходом, следовательно, p=2 или p=4 и s=78
if s >= 78 and (p == 2 or p == 4):
return True
# можно поставить просто 1
#
у Вани нет стратегии, которая позволяет ему гарантированно выиграть первым или вторым ходом
#
поэтому оставляем p=4
if s < 78 and p == 4:
return False
# можно поставить просто 0
if s >= 78 and p < 4:
return False
# если набрали 78 до третьего (p=4) хода, это ложь
# можно поставить просто 0
# прописываем правила игры для ее продолжения
# s+1 - добавить один камень
# s+3 - добавить три камня
# 4*s - увеличить количество камней в 4 раза
# p+1 - номер хода ВСЕГДА увеличивать на 1
# Петя ходит как угодно, поэтому прописываем следующее условие
if p % 2 != 0: # если похзиция нечетная, у Пети нечетные позиции (p=1 или p=3), то or
return f(s+1, p+1) or f(s+3, p+1) or f(4*s, p+1)
else: #
инача and
return f(s+1, p+1) and f(s+3, p+1) and f(4*s, p+1)
for s in range(1, 77):
if f(s, 0):
print(‘21: ', s)
32

33. Копируем предыдущий код и переделываем

# создаем функцию с условиями игры
def f(s, p):
# s - начальное количество камней в куче, p - номер хода
# победа у Вани, выигрыш СВОИМ первым или вторым ходом, следовательно, p=2 или p=4 и s=78
if s >= 78 and (p == 2 or p == 4):
return True
# можно поставить просто 1
#
у Вани нет стратегии, которая позволяет ему гарантированно выиграть первым или вторым ходом
#
поэтому оставляем p=4
if s < 78 and p == 4:
return False
# можно поставить просто 0
if s >= 78 and p < 4:
return False
# если набрали 78 до четвертого (p=4) хода, это ложь
# можно поставить просто 0
# прописываем правила игры для ее продолжения
# s+1 - добавить один камень
# s+3 - добавить три камня
# 4*s - увеличить количество камней в 4 раза
# p+1 - номер хода ВСЕГДА увеличивать на 1
# Петя ходит как угодно, поэтому прописываем следующее условие
if p % 2 != 0: # если позиция нечетная, у Пети нечетные позиции (p=1 или p=3), то or
return f(s+1, p+1) or f(s+3, p+1) or f(4*s, p+1)
else: #
инача and
return f(s+1, p+1) and f(s+3, p+1) and f(4*s, p+1)
for s in range(1, 77):
if f(s, 0):
print(‘21: ', s)
33

34. Копируем предыдущий код и переделываем

# создаем функцию с условиями игры
def f(s, p):
# s - начальное количество камней в куче, p - номер хода
# победа у Вани, выигрыш СВОИМ первым или вторым ходом, следовательно, p=2 или p=4 и s=78
if s >= 78 and (p == 2 or p == 4):
return True
# можно поставить просто 1
#
у Вас нет стратегии, которая позволяет ему гарантированно выиграть первым или вторым ходом
#
поэтому оставляем p=4
if s < 78 and p == 4:
return False
# можно поставить просто 0
if s >= 78 and p < 4:
return False
# если набрали 78 до четвертого (p=4) хода, это ложь
# можно поставить просто 0
# прописываем правила игры для ее продолжения
# s+1 - добавить один камень
# s+3 - добавить три камня
# 4*s - увеличить количество камней в 4 раза
# p+1 - номер хода ВСЕГДА увеличивать на 1
# Петя ходит как угодно, поэтому прописываем следующее условие
if p % 2 != 0: # если позиция нечетная, у Пети нечетные позиции (p=1 или p=3), то or
return f(s+1, p+1) or f(s+3, p+1) or f(4*s, p+1)
else: #
иначе and
return f(s+1, p+1) and f(s+3, p+1) and f(4*s, p+1)
for s in range(1, 77):
if f(s, 0):
print(‘21: ', s)
34

35. Копируем предыдущий код и переделываем

# создаем функцию с условиями игры
def f(s, p):
# s - начальное количество камней в куче, p - номер хода
# победа у Вани, выигрыш СВОИМ первым или вторым ходом, следовательно, p=2 или p=4 и s=78
if s >= 78 and (p == 2 or p == 4):
return True
# можно поставить просто 1
#
у Васи нет стратегии, которая позволяет ему гарантированно выиграть первым или вторым ходом
#
поэтому оставляем p=4
if s < 78 and p == 4:
return False
# можно поставить просто 0
if s >= 78 and p < 4:
return False
# если набрали 78 до четвертого (p=4) хода, это ложь
# можно поставить просто 0
# прописываем правила игры для ее продолжения
# s+1 - добавить один камень
# s+3 - добавить три камня
# 4*s - увеличить количество камней в 4 раза
# p+1 - номер хода ВСЕГДА увеличивать на 1
# Петя ходит как угодно, поэтому прописываем следующее условие
if p % 2 != 0: # если позиция нечетная, у Пети нечетные позиции (p=1 или p=3), то or
return f(s+1, p+1) or f(s+3, p+1) or f(4*s, p+1)
else: #
иначе and
return f(s+1, p+1) and f(s+3, p+1) and f(4*s, p+1)
Результат работы
программы:
21: 15
21: 17
21: 19
for s in range(1, 78):
if f(s, 0):
print(‘21: ', s)
35

36. Копируем предыдущий код и переделываем

# создаем функцию с условиями игры
def f(s, p):
# s - начальное количество камней в куче, p - номер хода
# победа у Вани, выигрыш СВОИМ первым или вторым ходом, следовательно, p=2 или p=4 и s=78
if s >= 78 and (p == 2 or p == 4):
return True
# можно поставить просто 1
#
у Вани нет стратегии, которая позволяет ему гарантированно выиграть первым или вторым ходом
#
поэтому оставляем p=4
if s < 78 and p == 4:
return False
# можно поставить просто 0
if s >= 78 and p < 4:
return False
# если набрали 78 до четвертого (p=4) хода, это ложь
# можно поставить просто 0
# прописываем правила игры для ее продолжения
# s+1 - добавить один камень
# s+3 - добавить три камня
# 4*s - увеличить количество камней в 4 раза
# p+1 - номер хода ВСЕГДА увеличивать на 1
# Петя ходит как угодно, поэтому прописываем следующее условие
if p % 2 != 0: # если позиция нечетная, у Пети нечетные позиции (p=1 или p=3), то or
return f(s+1, p+1) or f(s+3, p+1) or f(4*s, p+1)
else: #
иначе and
return f(s+1, p+1) and f(s+3, p+1) and f(4*s, p+1)
for s in range(1, 78):
if f(s, 0):
Результат работы
программы:
21: 15
21: 17
21: 19
Ответ:
21: 15
print(‘21: ', s)
36

37. Одна куча – уменьшение (ЕГЭ-19-21)

Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя.
За один ход игрок может убрать из кучи 5 камней или уменьшить количество камней в 3 раза. Убирать 5 камней можно только тогда, когда в
куче есть не менее 5 камней. Если количество камней некратно 3, то при уменьшении количества камней в три раза остается количество
камней равное результату целочисленного деления текущего количества на 3.
Например, из кучи из 19 камней можно получить кучу из 14 камней или кучу из 6 камней. Игра завершается в тот момент, когда из кучи
убирается последний камень. Победителем считается игрок, сделавший последний ход, т. е. убравший из кучи последний камень.
В начальный момент в куче было S камней; S > 0.
Ответьте на следующие вопросы:
Вопрос 1. Укажите максимальное значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть
своим первым ходом.
Вопрос 2. Найдите наименьшее и наибольшее значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются
два условия:
1.
Петя не может выиграть за один ход;
2.
Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Вопрос 3. Найдите максимальное значение S, при котором одновременно выполняются два условия:
1.
у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
2.
у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом;
Петя может выбирать, каким ходом выиграет Ваня.
37

38. Одна куча – уменьшение (ЕГЭ-19)

38

39. Одна куча – уменьшение (ЕГЭ-20)

39

40. Одна куча – уменьшение (ЕГЭ-20)

40

41. Одна куча – уменьшение (ЕГЭ-20)

41

42. Одна куча – уменьшение (ЕГЭ-21)

42

43. Домашнее задание

Изучить разбор задач разных типов на сайте
https://kpolyakov.spb.ru/school/ege.htm
43

44. Информатика

ЕГЭ-27
Тема: Анализ данных
Задание проверяет умение решать задачи анализа данных

45. Условие

Учёный решил провести кластеризацию некоторого множества звёзд по их расположению на карте
звёздного неба.
Кластер звёзд – это набор звёзд (точек) на графике, лежащий внутри прямоугольника
высотой H и шириной W.
Каждая звезда обязательно принадлежит только одному из кластеров.
Истинный центр кластера, или центроид, – это одна из звёзд на графике, сумма расстояний от которой
до всех остальных звёзд кластера минимальна.
В файле A хранятся данные о звёздах двух кластеров, где H=3, W=3 для каждого кластера. В каждой
строке записана информация о расположении на карте одной звезды: сначала координата x, затем координата y.
Значения даны в условных единицах. Известно, что количество звёзд не превышает 1000.
В файле Б хранятся данные о звёздах трёх кластеров, где H=3, W=3 для каждого кластера. Известно, что
количество звёзд не превышает 10 000. Структура хранения информации о звездах в файле Б аналогична файлу А.
Для каждого файла
В ответе запишите четыре числа:
определите координаты центра каждого кластера, затем • в первой строке сначала целую часть произведения
вычислите два числа:
Px × 10 000 , затем
• Px – среднее арифметическое абсцисс центров
• целую часть произведения Py × 10 000 для файла А,
кластеров, и
• во второй строке – аналогичные данные для файла Б.
• Py – среднее арифметическое ординат центров
кластеров.
45

46. Возможные данные одного из файлов иллюстрированы графиком:

Под расстоянием понимается расстояние Евклида между двумя точками A(x1, y1) и B(x2, y2) на плоскости,
которое вычисляется по формуле:
46

47. Замечание

Итак, в задании нужно решить две похожих задачи с разным количеством данных и
записать по два ответа на каждую задачу.
К заданию прилагаются четыре файла, для решения пригодятся все четыре.
В текстовом файле и в таблице для каждой задачи содержатся одинаковые данные
– координаты звёзд (точек). Например, в файлах А:
В Excel отображается меньше знаков
после запятой, при желании можно
увеличить количество знаков и убедиться,
что числа одни и те же.
В файлах А координат не более 1 000, в
файлах Б – не более 10 000.
Звёзды (точки) в файлах А
распределяются по двум кластерам, а в
файлах Б – по трём.
Размер кластера одинаков для А и для Б
это прямоугольник 3 на 3.
47

48. План решения

1) Определим примерные координаты каждого кластера
2) Подготовим данные в текстовом файле для программной
обработки
(Можно обойтись и без этого, но тогда нужно будет учитывать эту подготовку в самой программе)
3) Напишем программу на Python для расчёта центроида для
каждого кластера и средних арифметических по абсциссам и
ординатам центроидов.
48

49. Решение задачи А

1) Определим примерные координаты каждого кластера
• Построим в Excel точечную диаграмму
Выделить данные Вставка Точечная диаграмма
• Определим примерные границы каждого кластера
К первому кластеру отнесём точки (звёзды) с координатой X
от -2 до 1 и координатой Y от 0 до 3
• Исходя из условия задачи, все оставшиеся точки точно будут
относиться ко второму кластеру
• Если бы это не было известно, мы бы так же определили
диапазон координат второго кластера
49

50. 2) Подготовим данные в текстовом файле для программной обработки

Удаляем из файла первую строку с X и Y
Меняем все запятые на точки (Ctrl+H, заменить все)
(В файле дробная часть числа отделена от целой части
запятой. Это нужно для преобразования считанных из
файла текстовых данных в числа)
50

51. 3) Напишем программу на Python для расчёта центроида для каждого кластера и средних арифметических по абсциссам и ординатам

центроидов
• Для кластеров создадим два пустых списка:
Cluster1, cluster2 = [], []
51

52. 3) Напишем программу на Python для расчёта центроида для каждого кластера и средних арифметических по абсциссам и ординатам

центроидов
• Для кластеров создадим два пустых списка:
Cluster1, cluster2 = [], []
Откроем файл (файл с программой и файлы к заданию находятся в одной
папке)
With open (‘demo_2025_27_A.txt) as file:
52

53. 3) Напишем программу на Python для расчёта центроида для каждого кластера и средних арифметических по абсциссам и ординатам

центроидов
• Для кластеров создадим два пустых списка:
Cluster1, cluster2 = [], []
Откроем файл (файл с программой и файлы к заданию находятся в одной
папке)
With open (‘demo_2025_27_A.txt) as file:
Считаем построчно координаты, распределяя их по кластерам:
for line in file:
x, y = [float(a) for a in line.split()]
if -2 <= x <= 1 and 0<=y <=3:
cluster1.append((x,y))
else: cluster2.append((x, y))
53

54.

• Для определения координат центроида кластера напишем функцию, в которой
будем искать минимальную сумму расстояний Евклида по формуле.
def centroid(cluster):
minimum = 18*1000
x, y = 0, 0
for I in range(len(cluster)):
sum_d=0
for j in range(len(cluster)):
sum_d += ((cluster[i][0]-cluster[j][0])**2 + (cluster[i][1]-cluster[j][1])**2)**0.5
if sum_d < minimum:
minimum = sum_d
x, y = cluster[i][0],cluster[i][1]
return x, y
Функция вернёт координаты центроида.
54

55.

• Получив результат по двум кластерам, останется посчитать среднее
арифметическое отдельно по координатам X и Y и вывести результат в заданном
формате – целую часть после умножения на 10 000.
x1, y1 = centroid(cluster1)
x2, y2 = centroid(cluster2)
print(int((x1+x2)/2*10000, int((y1+y2)/2*10000))
55

56. Решение задачи В

Первые два этапа такие же, как в решении задачи А
На третьем этапе копируем написанную для первой
задачи программу и вносим в неё изменения.
В файлах Б 10 000 точек и три кластера.
Если проверять точку на принадлежность каждому
кластеру, то неплохо бы сверить сумму
распределённых точек с их общим количеством.
Так мы убедимся, что все точки распределены.
Программа работает заметно дольше.
56

57. Запись ответа

Ответ записывается в две строки.
В первой – результаты по файлам А, во второй – по Б:
10738 30730
37522 51277
57