Задание 26. Алгоритмы сортировки. Обработка целочисленной информации.. ЕГЭ 2024 по информатике
Средний процент выполнения: 48.6%
Ответом к заданию 26 по информатике может быть развернутый ответ (полная запись решения с обоснованием выполненных действий).
Задачи для практики
Задача 1
Спортсмены на дисциплине «Прыжки в длину» пытаются победить в соревновании. Каждому спортсмену даётся 3 попытки, из которых выбирается лучшая. Найдите значение лучшего прыжка спорстмена, который занял 10-ое место.
Входные данные: в первой строке вводится число N (натуральное, не превышает 1000) — количество спортсменов на соревновании, в каждой из следующих N строк записано три числа (Натуральные, не превышает 10000) — длина прыжка в сантиметрах в каждой из трёх попыток.
Выходные данные: одно число — значение лучшего прыжка спорстмена, который занял 10-ое место.
В качестве ответа на это задание прикрепите код программы, а также напишите ответ, который выдала программа для прикреплённого файла.
Решение
Пример решения на Python:
def bubble_sort(a):
for i in range(len(a)):
for j in range(len(a) — 1 — i):
if a[j] < a[j+1]:
a[j], a[j+1] = a[j+1], a[j]
f = open(«file.txt»)
i = 0
a = []
for st in f:
if i == 0:
N = int(st)
else:
n1, n2, n3 = map(int, st.split())
a.append(max(n1,n2,n3))
i += 1
bubble_sort(a)
print(a[9])
f.close()
Для прикреплённого файла программа выведет: 9973
Задача 2
Спортсмены на дисциплине «Прыжки в длину» пытаются победить в соревновании. Каждому спортсмену даётся 3 попытки, из которых выбирается лучшая. Найдите значение лучшего прыжка спорстмена, который занял 10-ое место.
Входные данные: в первой строке вводится число N (натуральное, не превышает 1000) — количество спортсменов на соревновании, в каждой из следующих N строк записано три числа (Натуральные, не превышает 10000) — длина прыжка в сантиметрах в каждой из трёх попыток.
Выходные данные: одно число — значение лучшего прыжка спорстмена, который занял 10-ое место.
В качестве ответа на это задание прикрепите код программы, а также напишите ответ, который выдала программа для прикреплённого файла.
Решение
Пример решения на Python:
def bubble_sort(a):
for i in range(len(a)):
for j in range(len(a) — 1 — i):
if a[j] < a[j+1]:
a[j], a[j+1] = a[j+1], a[j]
f = open(«file.txt»)
i = 0
a = []
for st in f:
if i == 0:
N = int(st)
else:
n1, n2, n3 = map(int, st.split())
a.append(max(n1,n2,n3))
i += 1
bubble_sort(a)
print(a[9])
f.close()
Для прикреплённого файла программа выведет: 9964
Задача 3
В Высшей Школе Экологии на факультете Экологии K бюджетных мест. N абитуриентов подали документы на этот факультет. Определить проходной балл на факультете. Проходной балл — количество баллов у последнего прошедшего абитуриента.
Входные данные: в первой строке вводятся два числа. Число N (натуральное, не превышает 1000) — количество абитурентов, подавших документы. Число K (натуральное, не превышает N) — количество бюджетных мест. В каждой из следующих N строк записано одно число (Натуральное, не превышает 310) — баллы абитурента за экзамены.
Выходные данные: одно число — проходной балл на факультете.
Пример входных данных:
5 3
300
290
170
240
275
Пример выходных данных:
275
В качестве ответа на это задание прикрепите код программы, а также напишите ответ, который выдала программа для прикреплённого файла.
Решение
Отсортируем список по убыванию, а затем выведем значение элемента массива, который находится на K-ом месте. Пример решения на Python:
def bubble_sort(a):
for i in range(len(a)):
for j in range(len(a) — 1 — i):
if a[j] < a[j+1]:
a[j], a[j+1] = a[j+1], a[j]
f = open(«file.txt»)
i = 0
a = []
for st in f:
if i == 0:
N, K = map(int, st.split())
else:
a.append(int(st))
i += 1
bubble_sort(a)
print(a[K-1])
f.close()
Для прикреплённого файла программа выведет: 158
Задача 4
В магазине электроники «Эскалейдо» проводится рекламная акция. Каждый второй товар — бесплатно. Естественно, в руководстве магазина сидят умные люди, которые не хотят отдавать бесплатно Sony PS5 при покупке жвачки на кассе, поэтому хотят написать умный алгоритм, который поможет располагать пары «платный товар-бесплатный товар» таким образом, чтобы прибыль магазина была наибольшей. Задача: написать алгоритм, который определяет максимальную выручку магазина для каждого чека.
Входные данные: в первой строке вводится число N (натуральное, не превышает 1000) — количество товаров в чеке, в каждой из следующих N строк записано одно число (Натуральное, не превышает $10^6$) — стоимость купленного товара.
Выходные данные: одно число — максимальная выручка магазина с данного списка товаров.
Пример входных данных:
4
300
5000
600
900
Пример выходных данных:
5900
В качестве ответа на это задание прикрепите код программы, а также напишите ответ, который выдала программа для прикреплённого файла.
Решение
В итоговую стоимость пойдёт половина самых дорогих товаров. Поэтому нам необходимо отсортировать список по убыванию и посчитать сумму первой половины товаров (и ещё +1 товар для нечётного количества товаров). Пример решения на Python:
def bubble_sort(a):
for i in range(len(a)):
for j in range(len(a) — 1 — i):
if a[j] < a[j+1]:
a[j], a[j+1] = a[j+1], a[j]
f = open(«file.txt»)
i = 0
a = []
for st in f:
if i == 0:
N = int(st)
else:
a.append(int(st))
i += 1
bubble_sort(a)
s = 0
for i in range(N//2+N%2):
s += a[i]
print(s)
f.close()
Для прикреплённого файла программа выведет: 13428503
Задача 5
Фанаты музыкальной группы Rammstein организуют поездку на концерт. Фанатов очень много, для их перевозки нужны автобусы. У организатора есть количество людей, а также информация о вместимости всех автобусов, свободных на данные дни. Определите наименьшее количество автобусов, необходимых для размещения всех фанатов, а также минимальное количество пустующих мест в автобусе для наименьшего количества автобусов.
Входные данные
В первой строке входного файла находятся два числа: X — количество фанатов (натуральное число, не превышает 3000) и N — количество автобусов (натуральное число, не превышает 1000). В следующих N строках находятся значения количества мест в каждом автобусе (натуральные числа, не превышают 100), каждое в отдельной строке.
В качестве ответа прикрепите код решённой задачи, а также укажите два числа: наименьшее количество автобусов и наименьшее количество пустующих мест.
Пример входного файла:
100 4
70
50
20
40
Пример выходных данных:
2 10
Решение
Пример решения на языке Python:
def bubble_sort(a):
for i in range(len(a)):
for j in range(len(a) — 1 — i):
if a[j] < a[j+1]:
a[j], a[j+1] = a[j+1], a[j]
f = open(«file.txt»)
i = 0
a = []
for st in f:
if i == 0:
X, N = map(int, st.split())
else:
a.append(int(st))
i += 1
bubble_sort(a)
s = 0
i = -1
while s <= X:
i += 1
s += a[i]
kol = i+1
s -= a[i]
while i < N and s+a[i] >= X:
i += 1
print(kol, s+a[i-1]-X)
f.close()
Ответ, который выведет верная программа: 28 0
Задача 6
Грузчик Лёха закидывает мешки со строительным мусором в Газель. Мусора целая стройка, а Газель маленькая. Лёха хочет узнать, какое наибольшее количество мешков с мусором можно впихнуть в Газель, а также наибольший вес мешка, который можно погрузить в Газель при условии, что запихнули наибольшее количество мешков.
Входные данные
В первой строке входного файла находятся два числа: X — грузоподъёмность Газели в килограммах (натуральное число, не превышает 3000) и N — количество мешков с мусором (натуральное число, не превышает 1000). В следующих N строках находятся значения вес каждого мешка в килограммах (натуральные числа, не превышают 100), каждое в отдельной строке.
В качестве ответа прикрепите код решённой задачи, а также укажите два числа: наибольшее количество мешков и вес наибольшего мешка в Газели.
Пример входного файла:
100 4
70
50
20
40
Пример выходных данных:
2 70
Решение
Пример решения на языке Python:
def bubble_sort(a):
for i in range(len(a)):
for j in range(len(a) — 1 — i):
if a[j] > a[j+1]:
a[j], a[j+1] = a[j+1], a[j]
f = open(«file.txt»)
i = 0
a = []
for st in f:
if i == 0:
X, N = map(int, st.split())
else:
a.append(int(st))
i += 1
bubble_sort(a)
s = 0
i = -1
while s <= X:
i += 1
s += a[i]
s -= a[i]
s -= a[i-1]
kol = i
while i < N and s+a[i] <= X:
i += 1
print(kol, a[i-1])
f.close()
Ответ, который выведет верная программа: 212 32
Задача 7
Грузчик Лёха закидывает мешки со строительным мусором в Газель. Мусора целая стройка, а Газель маленькая. Лёха хочет узнать, какое наибольшее количество мешков с мусором можно впихнуть в Газель, а также наибольший запас веса, который останется в Газели при условии, что запихнули наибольшее количество мешков.
Входные данные
В первой строке входного файла находятся два числа: X — грузоподъёмность Газели в килограммах (натуральное число, не превышает 3000) и N — количество мешков с мусором (натуральное число, не превышает 1000). В следующих N строках находятся значения вес каждого мешка в килограммах (натуральные числа, не превышают 100), каждое в отдельной строке.
В качестве ответа прикрепите код решённой задачи, а также укажите два числа: наибольшее количество мешков и наибольший запас веса в Газели.
Пример входного файла:
100 4
70
50
20
40
Пример выходных данных:
2 40
Решение
Пример решения на языке Python:
def bubble_sort(a):
for i in range(len(a)):
for j in range(len(a) — 1 — i):
if a[j] > a[j+1]:
a[j], a[j+1] = a[j+1], a[j]
f = open(«file.txt»)
i = 0
a = []
for st in f:
if i == 0:
X, N = map(int, st.split())
else:
a.append(int(st))
i += 1
bubble_sort(a)
s = 0
i = -1
while s <= X:
i += 1
s += a[i]
s -= a[i]
print(i, X-s)
f.close()
Ответ, который выведет верная программа: 212 9
Задача 8
Грузчик Лёха закидывает мешки со строительным мусором в Газель. Мусора целая стройка, а Газель маленькая. Лёха хочет узнать, какое наибольшее количество мешков с мусором можно впихнуть в Газель, а также наибольший запас веса, который останется в Газели при условии, что запихнули наибольшее количество мешков.
Входные данные
В первой строке входного файла находятся два числа: X — грузоподъёмность Газели в килограммах (натуральное число, не превышает 3000) и N — количество мешков с мусором (натуральное число, не превышает 1000). В следующих N строках находятся значения вес каждого мешка в килограммах (натуральные числа, не превышают 100), каждое в отдельной строке.
В качестве ответа прикрепите код решённой задачи, а также укажите два числа: наибольшее количество мешков и наибольший запас веса в Газели.
Пример входного файла:
100 4
70
50
20
40
Пример выходных данных:
2 40
Решение
Пример решения на языке Python:
def bubble_sort(a):
for i in range(len(a)):
for j in range(len(a) — 1 — i):
if a[j] > a[j+1]:
a[j], a[j+1] = a[j+1], a[j]
f = open(«file.txt»)
i = 0
a = []
for st in f:
if i == 0:
X, N = map(int, st.split())
else:
a.append(int(st))
i += 1
bubble_sort(a)
s = 0
i = -1
while s <= X:
i += 1
s += a[i]
s -= a[i]
print(i, X-s)
f.close()
Ответ, который выведет верная программа: 228 16
Задача 9
У профессора Виссариона Леонидовича настолько обширная библиотека книг, что все они не вмещаются в книжные шкафы. Чтобы хотя бы частично решить свою проблему, Виссарион Леонидович прикрутил к стене полку длиной X миллиметров. Он хочет узнать, какое наибольшее количество книг можно поставить на эту полку, а также размер наибольшего свободного пространства на полке при условии, что там стоит наибольшее количество книг.
Входные данные
В первой строке входного файла находятся два числа: X — длина полки в миллиметрах (натуральное число, не превышает 3000) и N — количество неразмещённых книг (натуральное число, не превышает 1000). В следующих N строках находятся значения толщин книг в миллиметрах (натуральные числа, не превышают 100), каждое в отдельной строке.
В качестве ответа прикрепите код решённой задачи, а также укажите два числа: наибольшее количество книг и размер наибольшего свободного пространства.
Пример входного файла:
100 4
70
50
20
40
Пример выходных данных:
2 40
Решение
Пример решения на языке Python:
def bubble_sort(a):
for i in range(len(a)):
for j in range(len(a) — 1 — i):
if a[j] > a[j+1]:
a[j], a[j+1] = a[j+1], a[j]
f = open(«file.txt»)
i = 0
a = []
for st in f:
if i == 0:
X, N = map(int, st.split())
else:
a.append(int(st))
i += 1
bubble_sort(a)
s = 0
i = -1
while s <= X:
i += 1
s += a[i]
s -= a[i]
print(i, X-s)
f.close()
Ответ, который выведет верная программа: 198 17
Задача 10
В Высшей Школе Экологии на факультете Экологии K бюджетных мест. N абитуриентов подали документы на этот факультет. Определить проходной балл на факультете. Проходной балл — количество баллов у последнего прошедшего абитуриента.
Входные данные: в первой строке вводятся два числа. Число N (натуральное, не превышает 1000) — количество абитурентов, подавших документы. Число K (натуральное, не превышает N) — количество бюджетных мест. В каждой из следующих N строк записано одно число (Натуральное, не превышает 310) — баллы абитурента за экзамены.
Выходные данные: одно число — проходной балл на факультете.
Пример входных данных:
5 3
300
290
170
240
275
Пример выходных данных:
275
Решение
Копируем данные из txt в Excel.
Запоминаем первую строчку и удаляем ее.
Сортируем то, что осталось, по убыванию и ищем балл 471-го студента.
Почему именно 471? Потому что именно столько бюджетных мест.
Задача 11
Два игрока, Коля и Саша, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Коля. За один ход игрок может добавить в одну из куч (по своему выбору) два камня или увеличить количество камней в куче в два раза. Например, пусть в одной куче 15 камней, а в другой — 20 камней; такую позицию будем обозначать (15; 20). Тогда за один ход можно получить любую из четырёх позиций (17; 20), (15; 22), (30; 20), (15; 40). У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в кучах становится не менее 100. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую позицию, при которой в кучах всего будет 100 камней или больше. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Например, при начальных позициях (50; 3), (35; 30), (40; 25) выигрышная стратегия есть у Коли. Чтобы выиграть, ему достаточно удвоить количество камней в первой куче.
Выполните следующие задания.
Задание 1. Для каждой из начальных позиций (10; 44), (20; 39) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.
Задание 2. Для каждой из начальных позиций (10; 42), (8; 44), (20; 37) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.
Задание 3. Для начальной позиции (8; 42) укажите, кто из игроков имеет выигрышную стратегию. Опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии. Постройте дерево всех партий, возможных при указанной вами выигрышной стратегии. Представьте дерево в виде рисунка или таблицы.
Решение
Задание 1. Если начальными являются позиции (10; 44), (20; 39), то выигрывает Саша своим первым ходом.
Если начальная позиция (10; 44), то после первого хода Коли может получиться одна из четырёх позиций: (12; 44) — всего 56, (20; 44) — всего 64, (10; 46) — всего 56, (10; 88) — всего 98. В каждом из полученных случаев суммарное число камней не превышает 100. Значит, Коля не может выиграть своим первым ходом. Для каждой из полученных позиций Саша, удвоив число камней во второй куче, получит соответственно позиции (12; 88), (20; 88), (10; 92), (10; 176).
В каждом случае суммарное число камней не менее 100. Следовательно, Саша выигрывает своим первым ходом.
Если начальная позиция (20; 39), то после первого хода Коли может получиться одна из четырёх позиций: (22; 39) всего 61, (40; 39) всего 79, (20; 41) всего 61, (20; 78) всего 98. В каждом из полученных случаев суммарное число камней не превышает 100. Значит, Коля не может выиграть своим первым ходом. Для каждой из полученных позиций Саша, удвоив число камней во второй куче, получит соответственно позиции (22; 78), (40; 78), (20; 82), (20; 156). В каждом случае суммарное число камней не менее 100. Следовательно, Саша выигрывает своим первым ходом.
Задание 2. Если начальными являются позиции (10; 42), (8; 44), (20; 37), то выигрывает Коля своим вторым ходом.
Если начальной является одна из позиций (10; 42) или (8; 44), то, чтобы выиграть, Коля должен после своего хода получить позицию (10; 44). Для этого он должен увеличить на 2 число камней либо во второй куче (для позиции (10; 42)), либо в первой (для позиции (8; 44)). Считая позицию (10; 44) начальной, мы приходим к рассмотрению ситуации задания 1.
Как уже было показано выше, в этом случае выигрывает тот, кто ходит вторым. Значит, выиграет Коля своим вторым ходом. Если начальная позиция (20; 37), то, чтобы выиграть, Коля должен увеличить во второй куче число камней на 2. Тогда после его хода получится позиция (20; 39). Считая эту позицию начальной, мы приходим к рассмотрению ситуации задания 1. Как уже было показано выше, в этом случае выигрывает тот, кто ходит вторым. Значит, выиграет Коля своим вторым ходом.
Задание 3. Если начальной является позиция (8; 42), то выигрывает Саша не более чем за два хода. После первого хода Коли из начальной позиции (8; 42) можно получить одну из следующих: (10; 42), (16; 42), (8; 44), (8; 84).
Если на начало хода Саши будет одна из позиций (10; 42), (8; 44), то он выиграет своим вторым ходом. Эти позиции были рассмотрены как начальные в задании 2. Если на начало хода Саши будет позиция (16; 42), то Саша, удвоив число камней во второй куче, получит позицию (16; 84) (здесь суммарное число камней 100) и выиграет.
Если на начало хода Саши будет позиция (8; 84), то Саша, удвоив число камней во второй куче, получит позицию (8; 168) (здесь суммарное число камней 176 > 100) и также выиграет. Таблица выигрышных ходов для позиции (8; 42). Заключительные позиции (в них выигрывает Саша) подчёркнуты.
| И. п. | Положение после очередных ходов | |||
| 1-й ход Коли (разобраны все ходы) | 1-й ход Саши (только ход по стратегии) | 2-й ход Коли (разобраны все ходы) | 2-й ход Саши (только ход по стратегии) | |
| (8; 42) | (10; 42) | (10; 44) | (12; 44) | (12; 88) |
| (20; 44) | (20; 88) | |||
| (10; 46) | (10; 92) | |||
| (10; 88) | (10; 176) | |||
| (8; 44) | (10; 44) | (12; 44) | (123; 29) | |
| (20; 44) | (360; 29) | |||
| (10; 46) | (120; 30) | |||
| (10; 88) | (120; 87) | |||
| (16; 42) | (16; 84) | |||
| (8; 84) | (8; 168) | |||
Задача 12
Найдите ряд с наибольшим номером, который удовлетворяет условию. В ответе запишите номер ряда и наименьший номер пикселя в ряду, удовлетворяющие условию.
Пример файла:
7
29 5
40 25
42 103
42 106
46 23
46 26
Для приведённого примера ответ будет: 46 24
Решение
Для решения этого номера можно использовать язык программирования или электронную таблицу.
Рассмотрим пример решения на Python
f = open('26_p.txt', 'r')
n = int(f.readline().strip())
x = [list(map(int, line.strip().split())) for line in f]
x.sort()
max_row = 0
pixel = 0
for i in range(n - 1):
if x[i][0] == x[i + 1][0] and x[i][1] + 3 == x[i + 1][1]:
if max_row < x[i][0]:
max_row = x[i][0]
pixel = x[i][1] + 1
print(max_row, pixel)
Ответ: 8631 7311
Задача 13
Спортсмены на дисциплине «Прыжки в длину» пытаются победить в соревновании. Каждому спортсмену даётся 3 попытки, из которых выбирается лучшая. Найдите значение лучшего прыжка спорстмена, который занял 10-ое место.
Входные данные: в первой строке вводится число N (натуральное, не превышает 1000) — количество спортсменов на соревновании, в каждой из следующих N строк записано три числа (Натуральные, не превышает 10000) — длина прыжка в сантиметрах в каждой из трёх попыток.
Выходные данные: одно число — значение лучшего прыжка спорстмена, который занял 10-ое место.
В качестве ответа на это задание прикрепите код программы, а также напишите ответ, который выдала программа для прикреплённого файла.
Решение
Пример решения на Python:
def bubble_sort(a):
for i in range(len(a)):
for j in range(len(a) — 1 — i):
if a[j] < a[j+1]:
a[j], a[j+1] = a[j+1], a[j]
f = open(«file.txt»)
i = 0
a = []
for st in f:
if i == 0:
N = int(st)
else:
n1, n2, n3 = map(int, st.split())
a.append(max(n1,n2,n3))
i += 1
bubble_sort(a)
print(a[9])
f.close()
Для прикреплённого файла программа выведет: 9979
Задача 14
Два игрока, Паша и Вова, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в три раза. Например, пусть в одной куче 20 камней, а в другой — 10 камней; такую позицию в игре будем обозначать (20, 10). Тогда за один ход можно получить любую из четырёх позиций: (21, 10), (60, 10), (20, 11), (20, 30).
Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 167. Победителем считается игрок, сделавший последний ход, то есть первым получивший такую позицию, что в кучах всего будет 167 или больше камней. В начальный момент в первой куче было 40 камней, во второй куче—S камней; 1 ≤ S ≤ 160.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока—значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Выполните следующие задания. Во всех случаях обосновывайте свой ответ.
Задание 1. а) Укажите все такие значения числа S, при которых Паша может выиграть за один ход и соответствующие выигрышные ходы. Если при некотором значении S Паша может выиграть несколькими способами, достаточно указать один выигрышный ход.
б) Укажите, сколько существует значений S, при которых Паша не может выиграть за один ход, но при любом ходе Паши Вова может выиграть своим первым ходом. Опишите выигрышную стратегию Вовы.
Задание 2. Укажите такое значение S, при котором у Паши есть выигрышная стратегия, причём одновременно выполняются два условия:
—Паша не может выиграть за один ход;
—Паша может выиграть своим вторым ходом независимо от того, как будет ходить Вова.
Для указанного значения S опишите выигрышную стратегию Паши.
Задание 3. Укажите значение S, при котором одновременно выполняются два условия:
— у Вовы есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Паши;
—у Вовы нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Для указанного значения S опишите выигрышную стратегию Вовы.
Постройте дерево всех партий, возможных при этой выигрышной стратегии Вовы (в виде рисунка или таблицы). На рёбрах дерева указывайте, кто делает ход, в узлах—количество камней в куче.
В заданиях 2 и 3 достаточно указать одно значение S и объяснить, почему это значение удовлетворяет условию соответствующего задания.
Решение
Пусть S —исходное количество камней во второй куче.
Задание 1. a) Паша может выиграть первым ходом, если S ∈ {43, 44, . . . , 160}.
Во всех случаях ему нужно удвоить количество камней во второй куче.
Если количество камней во второй куче меньше 43, то за один ход нельзя получить суммарное число камней в двух кучах более 166.
Задание 1. б) Вова может выиграть первым ходом (как бы ни играл Паша), если исходно во второй куче будет S = 42 камня, то есть начальной будет позиция (40, 42), то после первого хода Паши может получиться одна из четырёх позиций: (41, 42)— всего 83, (120, 42)—всего 162, (40, 43)—всего 83, (40, 126)— всего 166.
В каждом из полученных случаев суммарное число камней меньше, чем 169. Значит, Паша не может выиграть своим первым ходом. Для каждой из полученных позиций Вова, утроив число камней во второй куче, получит соответственно позиции (41, 126)—всего 167, (120, 126)—всего 246, (40, 129)—всего 169, (40, 378) — всего 418. В каждом случае суммарное число камней не менее 167. Следовательно, Вова выигрывает своим первым ходом.
Задание 2. Возможное значение S = 41 и 14. Если начальная позиция (40, 41), то Паша, чтобы выиграть своим вторым ходом, должен получить позицию (40, 42). Для этого ему нужно в кучу с 42 камнями добавить один камень. Считая позицию (40, 42) начальной, мы приходим к рассмотрению ситуации задания 1б.
При такой начальной позиции выигрывает второй игрок своим первым ходом. Значит, если начальной позицией будет (40, 41), то выиграет Паша своим вторым ходом.
Для позиции (40, 14) ситуация будет аналогичной, если первым ходом умножить на три количество камней во второй куче.
Задание 3. Возможное значение S = 40. Если начальная позиция (40, 40), то после первого хода Паши может получиться одна из четырёх позиций: (40, 41), (41, 40) — всего 81, (120, 40), (40, 120)—всего 160.
Если после хода Паши получены позиции (120, 40), (40, 120), то Вова, утроив число камней в куче со 120 камнями, получит позицию с суммарным числом камней, равным 400, и выиграет своим первым ходом.
Если после хода Паши получены позиции (40, 41), (41, 40), то Вова, увеличив в одной из куч число камней на 1, получит позиции (40, 42) или (42, 40) и, как было показано в ответе к заданию 1б, выиграет своим вторым ходом.
В таблице изображено дерево возможных партий при описанной стратегии Вовы. Заключительные позиции (в них выигрывает Вова) подчёркнуты.
| И. п. | Положение после очередных ходов | |||
| 1-й ход Паши (разобраны все ходы) |
1-й ход Вовы (только ход по стратегии) |
2-й ход Паши (разобраны все ходы) |
2-й ход Вовы (только ход по стратегии) |
|
| (40, 40) | (40, 41) | (40, 42) | (120, 42) | (120, 126) |
| (41, 42) | (41, 126) | |||
| (40, 126) | (40, 378) | |||
| (40, 43) | (40, 129) | |||
| (41, 40) | (42, 41) | (42, 120) | (126, 120) | |
| (42, 41) | (126, 41) | |||
| (126, 40) | (378, 40) | |||
| (43, 40) | (129, 40) | |||
| (120, 40) | (120, 120) | |||
| (40, 120) | (120, 120) | |||
Задача 15
Два игрока, Коля и Саша, играют в следующую игру. На столе в кучке лежат фишки. На лицевой стороне каждой фишки написано двузначное натуральное число, обе цифры которого находятся в диапазоне от 1 до 4. Никакие две фишки не повторяются. Игра состоит в том, что игроки поочередно берут из кучки по одной фишке и выкладывают в цепочку на стол лицевой стороной вверх таким образом, что каждая новая фишка ставится правее предыдущей и ближайшие цифры соседних фишек совпадают. Верхняя часть всех выложенных фишек направлена в одну сторону, то есть переворачивать фишки нельзя. Например, из фишки, на которой написано 12, нельзя сделать фишку, на которой написано 21.
Первый ход делает Коля, выкладывая на стол любую фишку из кучки. Игра заканчивается, когда в кучке нет ни одной фишки, которую можно добавить в цепочку. Тот, кто добавил в цепочку последнюю фишку, выигрывает, а его противник проигрывает.
Будем называть партией любую допустимую правилами последовательность ходов игроков, приводящую к завершению игры. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит указать, какую фишку он должен выставить в любой ситуации, которая ему может встретиться при различной игре противника.
Пример партии.
Пусть на столе в кучке лежат фишки: 11, 12, 13, 21, 22, 23.
Пусть первый ход Коли 21.
Саша может поставить 12, 11 или 13. Предположим, он ставит 12.Получим цепочку 21-12.
Коля может поставить 22 или 23. Предположим, он ставит 22. Получим цепочку 21-12-22.
Саша может поставить только фишку со значением 23. Получим цепочку 21-12-22-23.
Перед Колей в кучке остались только фишки 11 и 13, то есть нет фишек, которые он мог бы добавить в цепочку. Таким образом, партия закончена, Саша выиграл.
Выполните следующие три задания при исходном наборе фишек в кучке 11, 12, 13, 21, 22, 31, 33.
Задание 1. Приведите пример самой короткой партии, возможной при данном наборе фишек. Если таких партий несколько, достаточно привести одну.
Задание 2. Пусть Коля первым ходом пошёл 33. У кого из игроков есть выигрышная стратегия, позволяющая в этой ситуации выиграть своим третьим ходом? Постройте в виде рисунка или таблицы дерево всех партий, возможных при реализации выигрывающим игроком этой стратегии. На рёбрах дерева указывайте ход, в узлах — цепочку фишек, получившуюся после этого хода.
Задание 3. Укажите хотя бы один способ убрать 2 фишки из исходного набора так, чтобы всегда выигрывал не тот игрок, который имеет выигрышную стратегию в задании 2. Приведите пример партии для набора из 6 оставшихся фишек.
Решение
Задание 1. Пример кратчайшей партии: 21-12-22.
Возможны другие варианты ответа:
22-21-12;
31-13-33;
33-31-13.
Пояснение. Партия будет кратчайшей, если каждая фишка партии содержит одну и ту же цифру, которая встречается реже остальных. Ответный ход противника в случае кратчайшей партии должен быть «симметричным», если это возможно. То есть на ход фишкой «xy» ответным ходом должен быть «yx».
Задание 2. Стратегия, позволяющая выиграть своим третьим ходом, есть у Саши.
Ниже представлена таблица выигрышных стратегий Саши.
В таблице показаны все ходы Коли и только выигрышные ходы Саши. Заключительные позиции (в них выигрывает Саша) подчёркнуты.
| Коля 1-й ход |
33 33 |
|||
| Саша 1-й ход |
31 33-31 |
|||
| Коля 2-й ход |
32 11-13-32 |
13 33-31-13 |
12 33-31-12 |
|
| Саша 2-й ход |
12 33-31-11-12 |
— — |
22 33-31-12-22 |
|
| Коля 3-й ход |
21 33-31-11-12-21 |
22 33-31-11-12-22 |
— — |
21 33-31-12-22- 21 |
| Саша 3-й ход |
13 33-31-11-12-21-13 |
21 33-31-11-12-22-21 Игра не окончена |
— | 13 33-31-12-22-21-13 |
Пояснение. Стратегия Саши заключается в том, что он должен добавить ещё один дубль и не дать Коле поставить третий дубль; в этом случае количество фишек в партии будет чётным, что необходимо для выигрыша Саши.
Задание 3.Можно убрать фишки 22 и 33. В этом случае Коля выиграет третьим ходом. Стратегия Коли — обязательно поставить любым своим ходом фишку 11.
Пример такой партии:
| Игрок | Коля | Саша | Коля | Саша | Коля |
| Ход | 12 | 21 | 11 | 13 | 31 |
Пояснение. После того как из исходного набора будут убраны фишки «22», «33», останется нечётное количество фишек, при этом каждая фишка содержит 1 и у каждой фишки есть «симметричная» ей, поэтому первый игрок при правильной стратегии всегда выигрывает.
Задача 16
Два игрока, Коля и Саша, играют в следующую игру. На столе в кучке лежат фишки. На лицевой стороне каждой фишки написано двузначное натуральное число, обе цифры которого находятся в диапазоне от 1 до 4. Никакие две фишки не повторяются. Игра состоит в том, что игроки поочерёдно берут из кучки по одной фишке и выкладывают в цепочку на стол лицевой стороной вверх таким образом, что каждая новая фишка ставится правее предыдущей и ближайшие цифры соседних фишек совпадают. Верхняя часть всех выложенных фишек направлена в одну сторону, то есть переворачивать фишки нельзя. Например, из фишки, на которой написано 12, нельзя сделать фишку, на которой написано 21.
Первый ход делает Коля, выкладывая на стол любую фишку из кучки. Игра заканчивается, когда в кучке нет ни одной фишки, которую можно добавить в цепочку. Тот, кто добавил в цепочку последнюю фишку, выигрывает, а его противник проигрывает.
Будем называть партией любую допустимую правилами последовательность ходов игроков, приводящую к завершению игры. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Описать стратегию игрока—значит указать, какую фишку он должен выставить в любой ситуации, которая ему может встретиться при различной игре противника.
Пример партии.
Пусть на столе в кучке лежат фишки: 11, 12, 13, 21, 22, 23.
Пусть первый ход Коли 21.
Саша может поставить 12, 11 или 13. Предположим, он ставит 12.Получим цепочку 21-12.
Коля может поставить 22 или 23. Предположим, он ставит 22. Получим цепочку 21-12-22.
Саша может поставить только фишку со значением 23. Получим цепочку 21-12-22-23.
Перед Колей в кучке остались только фишки 11 и 13, то есть нет фишек, которые он мог бы добавить в цепочку. Таким образом, партия закончена, Саша выиграл.
Выполните следующие три задания при исходном наборе фишек в кучке {11, 12, 13, 21, 23, 31, 32, 33}.
Задание 1. Приведите пример самой короткой партии, возможной при данном наборе фишек. Если таких партий несколько, достаточно привести одну.
Задание 2. Пусть Коля первым ходом пошёл 11. У кого из игроков есть выигрышная стратегия, позволяющая в этой ситуации выиграть своим четвёртым ходом? Постройте в виде рисунка или таблицы дерево всех партий, возможных при реализации выигрывающим игроком этой стратегии. На рёбрах дерева указывайте ход, в узлах — цепочку фишек, получившуюся после этого хода.
Задание 3. Укажите хотя бы один способ убрать 2 фишки из исходного набора так, чтобы всегда выигрывал не тот игрок, который имеет выигрышную стратегию в задании 2. Приведите пример партии для набора из 6 оставшихся фишек.
Решение
Задание 1. Пример кратчайшей партии: 21-12-23-32.
Возможен другой вариант ответа: 23-32-21-12.
Пояснение: партия будет кратчайшей, если первый игрок начнёт игру с фишки, первая цифра которой встречается реже первых цифр остальных фишек, и, если это возможно, партия не содержит «дублей» — фишек вида «xx». Ответный ход противника, в случае кратчайшей партии, должен быть «симметричным», если это возможно. То есть на ход фишкой «xy» ответным ходом должен быть «yx», если это возможно.
Задание 2. Стратегия, позволяющая выиграть своим четвёртым ходом, есть у Коли.
Ниже представлена таблица выигрышных стратегий Коли. В таблице показаны все ходы Саши и только выигрышные ходы Коли. Заключительные позиции (в них выигрывает Коля) подчёркнуты.
| Коля 1-й ход |
11 11 |
||
| Саша 1-й ход |
12 11-12 |
13 11-13 |
|
| Коля 2-й ход |
21 11-12-21 |
32 11-13-32 |
|
| Саша 2-й ход |
13 11-12-21-13 |
23 11-13-32-23 |
21 11-13-32-21 |
| Коля 3-й ход |
32 11-12-21-13-32 |
31 11-13-32-23-31 |
12 11-13-32-21-12 |
| Саша 3-й ход |
23 11-12-21-13-32- 23 |
12 11-13-32-23-31- 12 |
23 11-13-32-21-12- 23 |
| Коля 4-й ход |
31 11-12-21-13-32- 23-31 |
21 11-13-32-23-31- 12-21 |
31 11-13-32-21-12- 23-31 |
Пояснение. Стратегия Коли заключается в том, что он должен ставить фишки, которые не заканчиваются на 3, тем самым не давая возможность Саше сделать ход «33». Например, если после ходов 11-13-31-12 Коля поставит фишку 23, то выиграет Саша: 11-13-31-12-23-33-32-21.
Задание 3.Можно убрать фишки 11 и 33. В этом случае независимо от ходов обоих игроков Саша выиграет (или своим вторым, или своим третьим ходом).
Пример такой партии:
| Игрок | Коля | Саша | Коля | Саша | Коля | Саша |
| Ход | 23 | 31 | 13 | 32 | 21 | 12 |
Пояснение. После того, как из исходного набора будут убраны фишки «11», «33», останется чётное количество фишек, при этом для каждой фишки есть «симметричная» ей, поэтому второй игрок всегда выигрывает.