Калужский Александр: Исправил!
05-09-2024
Читать статью
.: "Если число в двоичной форме имеет меньш..
Калужский Александр: Можно и так
02-09-2024
Привет! В этой статье мы порешаем нестандартные задачи из ЕГЭ по информатике в 19-21 Заданиях на теорию игр.
Как решать стандартные задачи, можете почитать в этой статье.
Приступим к подготовке!
(PRO100 ЕГЭ) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча снежков. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один снежок или увеличить количество снежков в куче в два раза. Для того чтобы лепить снежки, у каждого игрока есть неограниченное количество снега.
Игра завершается в тот момент, когда количество снежков в куче становится не менее 129. Проигравшим считается игрок, сделавший последний ход, т.е. первым получивший кучу из 129 или более снежков.
В начальный момент в куче было S снежков, 1 ≤ S ≤ 128.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
19. Укажите минимальное значение S, при котором при любой игре Пети Ваня может выиграть, сделав не более одного хода.
20. Для игры, описанной в задании 19, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
– Петя не может выиграть, сделав один ход; – Петя может выиграть, сделав не более двух ходов независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
21. Для игры, описанной в задании 19, найдите количество значений S, при которых одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть, сделав не более двух ходов при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть, сделав не более одного хода.
Условие задачи взято с сайта: https://stepik.org/lesson/1317775/step/6
Будем решать с конца данную задачу! В 19 Задании может выиграть Ваня на своём первом или "нулевом" ходе. Рассмотрим случай, когда Петя "загнан" в угол и обречён проиграть. Это значение 128.
Узнаем, как мы можем получить на его втором ходе это значение, посчитав обратные действия игроков.
Мы пришли к первоначальным значениям 126, 63 и 32.
Значения 32 и 63 не подходят, т.к. Петя на своём первом ходу не обязан действовать так, как нам хочется.
Например, 63 он может умножить на 2: 63*2 = 126, он не проигрывает, и мы сбиваемся с нашего дерева ходов, где уже было расписано так, чтобы наше условие удовлетворялось.
Тоже самое касается и числа 32. Петя просто свернёт в сторону 32+1=33. И снова мы сворачиваем с нашей благоприятной сетки ходов.
А вот число 126 нам подходит. Петя может попытаться уйти в сторону, например, 126*2 ≥ 129, но тогда он проигрывает и Ваня выигрывает за 0 ходов. Если Петя попробует сделать +1, то он пойдёт по сетке ходов, и снова Ваня выиграет за один ход.
Поэтому в 19 Задании ответ получается 126.
В 20 Задании Петя может выиграть или на первом ходе, или на втором своём ходе, но не может гарантировано выигрывать за 1 ход.
Вновь распишем благоприятную сетку, начиная с конца. Теперь проигрышное значение 128 должен получить Ваня.
Когда мы писали сетку, сразу отсеяли значения 63 и 32, которые может получить Ваня. Ведь он снова свернёт в сторону. Значение 63 можно умножить на 2 (63*2 = 126), к 32 можно прибавить 1 (32+1=33).
Значение 126 мы не отсеяли, т.к. к этому числу можно только прибавить единицу, иначе Ваня проиграет.
Остаётся только найти, при каких значениях мы для Вани организуем число 126, после первого хода Пети. Это числа 125 и 63.
Эти числа полностью подходят под условия. Либо Петя выиграет, сделав только один ход, либо выиграет, сделав два хода. Но у него нет возможности выиграть только после первого хода.
Ответ к 20 Заданию будет 63 и 125.
В 21 Задании должен выиграть Ваня.
Значения 63 и 32 после первого хода Вани можем отсеять сразу, т.к. Петя может свернуть в сторону, и он не проиграет.
Первоначальное значение 62 тоже не годится, т.к. сразу Петя на первом ходе может свернуть в сторону от благоприятной сетки, умножив это значение на 2.
Получается подходит только 124. Здесь, Петя не может свернуть в сторону, т.к. умножив 124 на 2 он проиграет. Получается, это значение подходит по всем параметрам. Ваня с этим числом выиграет либо сделав 0 ходов, либо сделав 1 ход, либо сделав 2 хода, но у Ваня не может гарантировано выиграть сделав 0 ходов или сделав 1 ход.
В ответе просили указать количество первоначальных значений, которые обеспечат условие задачи. У нас получилось одно значение.
В 21 Задании получается ответ 1.
19. Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может
Игра завершается в тот момент, когда количество камней в куче становится не менее 36. Если при этом в куче оказалось не более 60 камней, то победителем считается игрок, сделавший последний ход. В противном случае победителем становится его противник (при этом победа учитывается как ход противника). В начальный момент в куче было S камней, 1 ≤ S ≤ 35.
Найдите минимальное значение S, при котором Ваня выигрывает своим первым ходом при любой игре Пети.
20. Для игры, описанной в задании 19, определите сколько существует значений S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
21. Для игры, описанной в задании 19, найдите минимальное и максимальное значения S, при которых одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Условие задачи взято с сайта (№ 845): https://kompege.ru/task/
Начнём решать опять задачку с конца. Распишем значения, которые можно получить Ване, чтобы без проблем выиграть после первого хода.
Распишем дерево ходов назад и получим первоначальные значения. Красным цветом отмечены те значения, в которых Петя легко свернёт в сторону от благоприятной сетки или даже выиграет. Например, 17*3=51. А число 10 почти подходит, Петя может умножить на 2, тогда он попадёт в верхнюю ветку, он может умножить на 3, тогда попадёт в нижнюю ветку, но сделав ход +1, он свернёт с благоприятной сетки.
Таким образом, нам подходит только 34. Если попытаться его умножить на 2 или 3, то получается значение большее, чем 60.
Ответ к 19 Заданию 34.
Решим 20 Задание.
Те значения, которые были красным цветом, остаются красным, т.к. в этих значениях у Вани есть возможность свернуть с благоприятной сетки или выиграть.
Чтобы гарантировано выиграть на втором ходе после первого хода нужно получить число 34. Это можно сделать, если в начале было 33 камня, либо 17. Но 17 нам не подходит, т.к. у Пети есть возможность гарантировано выиграть первым ходом 17*3=51.
Значит, нам подходит только 33. В ответе напишем 1, т.е. одно значение.
В 20 Задании ответ будет 1.
Решим 21 Задание.
Значение 32 подходит, т.к. у Пети нет возможности свернуть в сторону. В крайнем случае Ваня выиграет за 0 ходов, если Петя сделает 32*2=64 или 32*3=96. Если он сделает +1, то попадает в благоприятную сетку, и Ваня выиграет на 2-ом своём ходе.
С числом 11 поинтереснее. С одной стороны, кажется, что у Пети есть возможность свернуть в сторону. Например, он сделает 11+1=12. Но значение 12 попадет в тот диапазон, из которого Ваня может выиграть первым ходом. Если Петя сделает 11*2=22, то вновь есть возможность выиграть за 1 ход, умножив это число на 2. Но, если Ваня умножит 11 на 3, то как раз он попадает в благоприятную сетку ходов, когда Ваня выигрывает за 2 хода.
При значении 11 у Вани нет гарантии выиграть первым ходом, т.к. 33*2 > 60 и 33*3 > 60.
В 21 Задании ответ будет 11 и 32.
Эти две задачи тяжело было сделать, модифицируя стандартный шаблон из этой статьи.
(PRO100 ЕГЭ) Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее 21. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу из 21 или больше камней.
В начальный момент в куче было S камней, 1 ≤ S ≤ 20.
19. Найдите минимальное значение S, при котором у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
– Петя не может выиграть за один ход;
– Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
20. Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:
21. Для игры, описанной в задании 19, найдите два минимальных значения S, при которых одновременно выполняются три условия:
– у Пети есть выигрышная стратегия, позволяющая ему выиграть первым, вторым или третьим ходом при любой игре Вани;
– у Пети нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
– у Пети нет стратегии, которая позволит ему гарантированно выиграть первым или вторым ходом.
Здесь стандартная 20 стала 19-ой, стандартная 21 задача стала 20-ой, а в 21 добавили ещё один ход в глубину.
def F(x, p): if x>=21 and p==4: return True if x<21 and p==4: return False if x>=21: return False if p%2==0: return F(x+1, p+1) and F(x*2, p+1) else: return F(x+1, p+1) or F(x*2, p+1) for s in range(1, 21): if F(s, 1): print(s)
Ответ в 19 Задачке будет 5.
def F(x, p): if x>=21 and (p==3 or p==5): return True if x<21 and p==5: return False if x>=21: return False if p%2==1: return F(x+1, p+1) and F(x*2, p+1) else: return F(x+1, p+1) or F(x*2, p+1) def F1(x, p): if x>=21 and p==3: return True if x<21 and p==3: return False if x>=21: return False if p%2==1: return F1(x+1, p+1) and F1(x*2, p+1) else: return F1(x+1, p+1) or F1(x*2, p+1) for s in range(1, 21): if F(s, 1): print(s) print() for s in range(1, 21): if F1(s, 1): print(s)
Ответ в 20 задачке будет 8.
def F(x, p): if x>=21 and (p==2 or p==4 or p==6): return True if x<21 and p==6: return False if x>=21: return False if p%2==0: return F(x+1, p+1) and F(x*2, p+1) else: return F(x+1, p+1) or F(x*2, p+1) def F1(x, p): if x>=21 and p==2: return True if x<21 and p==2: return False if x>=21: return False if p%2==0: return F1(x+1, p+1) and F1(x*2, p+1) else: return F1(x+1, p+1) or F1(x*2, p+1) def F2(x, p): if x>=21 and (p==2 or p==4): return True if x<21 and p==4: return False if x>=21: return False if p%2==0: return F2(x+1, p+1) and F2(x*2, p+1) else: return F2(x+1, p+1) or F2(x*2, p+1) for s in range(1, 21): if F(s, 1): print(s) print() for s in range(1, 21): if F1(s, 1): print(s) print() for s in range(1, 21): if F2(s, 1): print(s)
То, что получается в функциях F1 и F2 мы должны исключить из ответов.
Ответы в 21 задании получаются 4 и 7.
(PRO100 ЕГЭ) Два игрока играют в следующую игру. Перед ними лежат три кучки камней, в первой из которых 2, во второй – 3, в третьей – S (1 ≤ S ≤ 19) камней. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в какой-то куче или добавляет по два камня в каждую из куч.
Выигрывает игрок, после хода которого в одной из куч становится не менее 20 камней, или общее число камней во всех трех кучах становится не менее 25.
19. Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
20. Для игры, описанной в предыдущем задании, найдите два наименьших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
21. Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:
def F(x, y, z, p): if (x>=20 or y>=20 or z>=20 or x+y+z >= 25) and p==3: return True if not(x>=20 or y>=20 or z>=20 or x+y+z >= 25) and p==3: return False if (x>=20 or y>=20 or z>=20 or x+y+z >= 25): return False if p%2!=0: return F(x*2, y, z, p+1) and F(x, y*2, z, p+1) and F(x, y, z*2, p+1) and F(x+2, y+2, z+2, p+1) else: return F(x*2, y, z, p+1) or F(x, y*2, z, p+1) or F(x, y, z*2, p+1) or F(x+2, y+2, z+2, p+1) for s in range(1, 20): if F(2, 3, s, 1): print(s)
Ответ в 19 задании получается 9.
def F(x, y, z, p): if (x>=20 or y>=20 or z>=20 or x+y+z >= 25) and p==4: return True if not(x>=20 or y>=20 or z>=20 or x+y+z >= 25) and p==4: return False if (x>=20 or y>=20 or z>=20 or x+y+z >= 25): return False if p%2==0: return F(x*2, y, z, p+1) and F(x, y*2, z, p+1) and F(x, y, z*2, p+1) and F(x+2, y+2, z+2, p+1) else: return F(x*2, y, z, p+1) or F(x, y*2, z, p+1) or F(x, y, z*2, p+1) or F(x+2, y+2, z+2, p+1) for s in range(1, 20): if F(2, 3, s, 1): print(s)
В 20 Задании получаются ответы 2 и 3.
def F(x, y, z, p): if (x>=20 or y>=20 or z>=20 or x+y+z >= 25) and (p==3 or p==5): return True if not(x>=20 or y>=20 or z>=20 or x+y+z >= 25) and p==5: return False if (x>=20 or y>=20 or z>=20 or x+y+z >= 25): return False if p%2!=0: return F(x*2, y, z, p+1) and F(x, y*2, z, p+1) and F(x, y, z*2, p+1) and F(x+2, y+2, z+2, p+1) else: return F(x*2, y, z, p+1) or F(x, y*2, z, p+1) or F(x, y, z*2, p+1) or F(x+2, y+2, z+2, p+1) def F1(x, y, z, p): if (x>=20 or y>=20 or z>=20 or x+y+z >= 25) and p==3: return True if not(x>=20 or y>=20 or z>=20 or x+y+z >= 25) and p==3: return False if (x>=20 or y>=20 or z>=20 or x+y+z >= 25): return False if p%2!=0: return F1(x*2, y, z, p+1) and F(x, y*2, z, p+1) and F1(x, y, z*2, p+1) and F1(x+2, y+2, z+2, p+1) else: return F1(x*2, y, z, p+1) or F1(x, y*2, z, p+1) or F1(x, y, z*2, p+1) or F1(x+2, y+2, z+2, p+1) for s in range(1, 20): if F(2, 3, s, 1): print(s) print() for s in range(1, 20): if F1(2, 3, s, 1): print(s)
В 21 Задании ответ получается 6.
Так же обратите внимание на задачу про фишки в статье https://stepik.org/lesson/1317775/step/6. Кажется, что это новая задача про какие-то фишки, но на самом деле это стандартная задача, которая решается с помощью шаблона из статьи.
В задачах, где камни не добавляют, а убирают, если она стандартная, можно применить обычный шаблон. Это показано в видео:
Надеюсь, хоть чуть-чуть Вам поможет эта статья на ЕГЭ по информатике.
