Ошибка.
Попробуйте повторить позже
Для игры, описанной в задании , найдите значение , при котором у Вани есть выигрышная стратегия, позволяющая ему выиграть вторым ходом при любой игре Пети, но у Вани нет стратегии, которая позволяла бы ему гарантированно выиграть первым ходом.
Решение руками
Мы знаем, что это позиция типа . Тогда рассмотрим
Решение программой
from functools import lru_cache def moves(heap): h, k = heap m = [] if k != 0: m += [(h + 1, 0)] if k != 1: m += [(h + 2, 1)] if k != 2: m += [(h * 3, 2)] return m @lru_cache(None) def game(heap): if heap[0] >= 50: return ’END’ elif any(game(x) == ’END’ for x in moves(heap)): return ’P1’ elif all(game(x) == ’P1’ for x in moves(heap)): return ’V1’ elif any(game(x) == ’V1’ for x in moves(heap)): return ’P2’ elif all(game(x) == ’P1’ or game(x) == ’P2’ for x in moves(heap)): return ’V2’ for s in range(1, 50): if game((s, -1)) == ’V2’: print(s)
Ошибка.
Попробуйте повторить позже
Для игры, описанной в предыдущем задании, существует несколько таких значений , при которых у Пети есть выигрышная стратегия, причём Петя не может выиграть первым ходом, но может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найдите наименьшее и наибольшее из таких значений . В ответе, запишите сначала наименьшее, затем наибольшее значение, без пробелов и знаков препинания.
Решение руками
Рассмотрим позицию Из неё Петя сходит в позицию утроением камней, после чего Ваня не сможет утроить кучу, и сходит либо в либо в Из этих позиций Петя выигрывает утроением камней. Также рассмотрим позицию Из неё Петя сходит в а это позиция типа .
Решение программой
from functools import lru_cache def moves(heap): h, k = heap m = [] if k != 0: m += [(h + 1, 0)] if k != 1: m += [(h + 2, 1)] if k != 2: m += [(h * 3, 2)] return m @lru_cache(None) def game(heap): if heap[0] >= 50: return ’END’ elif any(game(x) == ’END’ for x in moves(heap)): return ’P1’ elif all(game(x) == ’P1’ for x in moves(heap)): return ’V1’ elif any(game(x) == ’V1’ for x in moves(heap)): return ’P2’ elif all(game(x) == ’P1’ or game(x) == ’P2’ for x in moves(heap)): return ’V2’ for s in range(1, 50): if game((s, -1)) == ’P2’: print(s)
Ошибка.
Попробуйте повторить позже
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить два камня или увеличить количество камней в куче в три раза. При этом нельзя повторять ход, который только что сделал второй игрок.
Например, если в начале игры в куче камня, Петя может первым ходом получить кучу из или камней. Если Петя получил кучу из камней (добавил камня), то следующим ходом Ваня может получить или камней. Получить камней Ваня не может, так как для этого нужно добавить камня, а такой ход только что сделал Петя.
Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается, когда количество камней в куче становится не менее . Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет или больше камней.
В начальный момент в куче было камней,
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите такое значение при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Решение руками
Для начала найдём все позиции . Это позиции Рассмотрим позицию Из неё Петя утроением камней достигнет позиции из которой Ваня выиграет добавив в кучу камня.
Решение программой
from functools import lru_cache def moves(heap): h, k = heap m = [] if k != 0: m += [(h + 1, 0)] if k != 1: m += [(h + 2, 1)] if k != 2: m += [(h * 3, 2)] return m @lru_cache(None) def game(heap): if heap[0] >= 50: return ’END’ elif any(game(x) == ’END’ for x in moves(heap)): return ’P1’ elif all(game(x) == ’P1’ for x in moves(heap)): return ’V1’ elif any(game(x) == ’V1’ for x in moves(heap)): return ’P2’ elif all(game(x) == ’P1’ or game(x) == ’P2’ for x in moves(heap)): return ’V2’ for s in range(1, 50): if game((s, -1)) == ’V1’: print(s)
Ошибка.
Попробуйте повторить позже
Для игры, описанной в задании найдите два таких значения при которых одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
В ответе запишите числа в порядке возрастания без пробелов и знаков препинаний.
Решение руками
Рассмотрим . Из этой позиции Петя сможет сходить только в а мы знаем, что это позиция . Теперь рассмотрим позицию
Решение программой
from functools import lru_cache def moves(heap): m = [] if (heap + 1) % 2 != 0: m += [heap + 1] if (heap + 3) % 2 != 0: m += [heap + 3] if (heap * 3) % 2 != 0: m += [heap * 3] return m @lru_cache(None) def game(heap): if heap >= 63: return ’END’ elif any(game(x) == ’END’ for x in moves(heap)): return ’WIN1’ elif all(game(x) == ’WIN1’ for x in moves(heap)): return ’LOSE1’ elif any(game(x) == ’LOSE1’ for x in moves(heap)): return ’WIN2’ elif all(game(x) == ’WIN1’ or game(x) == ’WIN2’ for x in moves(heap)): return ’LOSE2’ for s in range(1, 63): if game(s) == ’LOSE2’: print(s)
Ошибка.
Попробуйте повторить позже
Для игры, описанной в предыдущем задании, найдите минимальное и максимальное значения при которых у Пети есть выигрышная стратегия, причём Петя не может выиграть за один ход и Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
В ответе запишите числа в порядке возрастания без пробелов и знаков препинаний.
Решение руками
Рассмотрим Первым ходом Петя достигнет позиции из которой Ваня не сможет сделать никаких ходов, кроме утроения, что приведёт Петю в позицию из которой он победит утроением. Теперь рассмотрим Первым ходом Петя сходит в позицию из которой Ваня сможет сходить лишь в из которой Петя победит также утроением.
Решение программой
from functools import lru_cache def moves(heap): m = [] if (heap + 1) % 2 != 0: m += [heap + 1] if (heap + 3) % 2 != 0: m += [heap + 3] if (heap * 3) % 2 != 0: m += [heap * 3] return m @lru_cache(None) def game(heap): if heap >= 63: return ’END’ elif any(game(x) == ’END’ for x in moves(heap)): return ’WIN1’ elif all(game(x) == ’WIN1’ for x in moves(heap)): return ’LOSE1’ elif any(game(x) == ’LOSE1’ for x in moves(heap)): return ’WIN2’ elif all(game(x) == ’WIN1’ or game(x) == ’WIN2’ for x in moves(heap)): return ’LOSE2’ for s in range(1, 63): if game(s) == ’WIN2’: print(s)
Ошибка.
Попробуйте повторить позже
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или три камня или увеличить количество камней в куче в раза, при этом после каждого хода в куче должно быть нечетное количество камней. Например, пусть в куче будет камней. Тогда за один ход можно получить кучу из или Игра завершается в тот момент, когда количество камней в куче становится не менее
Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в куче будет или более камней. В начальный момент в куче было камней .
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от игры противника.
Найдите минимальное значение при котором Ваня выигрывает своим первым ходом при любой игре Пети.
Решение руками
Для начала найдём все позиции типа . Это позиции и все нечётные позиции Тогда из позиции Петя может сходить только в и Ваня также умножит количество камней в куче на и победит.
Решение программой
from functools import lru_cache def moves(heap): m = [] if (heap + 1) % 2 != 0: m += [heap + 1] if (heap + 3) % 2 != 0: m += [heap + 3] if (heap * 3) % 2 != 0: m += [heap * 3] return m @lru_cache(None) def game(heap): if heap >= 63: return ’END’ elif any(game(x) == ’END’ for x in moves(heap)): return ’WIN1’ elif all(game(x) == ’WIN1’ for x in moves(heap)): return ’LOSE1’ elif any(game(x) == ’LOSE1’ for x in moves(heap)): return ’WIN2’ elif all(game(x) == ’WIN1’ or game(x) == ’WIN2’ for x in moves(heap)): return ’LOSE2’ for s in range(1, 63): if game(s) == ’LOSE1’: print(s) break
Ошибка.
Попробуйте повторить позже
Для игры, описанной в задании найдите минимальное значение при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Решение руками
Рассмотрим Из этой позиции Петя может сходить в или а из этих позиций Ваня сходит либо в , либо в а мы знаем, что это позиции типа .
Решение программой
from functools import lru_cache def moves(heap): m = [] if heap % 2 == 0: m += [heap // 2] else: if heap > 1: m += [heap - 2] if heap % 3 == 0: m += [heap // 3] else: if heap > 2: m += [heap - 3] return m @lru_cache(None) def game(heap): if heap <= 2: return 0 steps = [game(x) for x in moves(heap)] if any(x % 2 == 0 for x in steps): return min(x for x in steps if x % 2 == 0) + 1 return max(steps) + 1 for s in range(3, 100): if game(s) == 4: print(s) break
Ошибка.
Попробуйте повторить позже
Для игры, описанной в предыдущем задании, найдите минимальное и максимальное значения при которых у Пети есть выигрышная стратегия, причём Петя не может выиграть за один ход и Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
В ответе запишите числа в порядке возрастания без пробелов и знаков препинаний.
Решение руками
Для начала давайте найдём все позиции . Это все Теперь найдём все позиции . Это позиции Рассмотрим позицию Уменьшение на приведёт нас в а это . Теперь Рассмотрим позицию Уменьшение в раза приведёт нас в а это . Пишем их в ответ.
Решение программой
from functools import lru_cache def moves(heap): m = [] if heap % 2 == 0: m += [heap // 2] else: if heap > 1: m += [heap - 2] if heap % 3 == 0: m += [heap // 3] else: if heap > 2: m += [heap - 3] return m @lru_cache(None) def game(heap): if heap <= 2: return 0 steps = [game(x) for x in moves(heap)] if any(x % 2 == 0 for x in steps): return min(x for x in steps if x % 2 == 0) + 1 return max(steps) + 1 for s in range(3, 100): if game(s) == 3: print(s)
Ошибка.
Попробуйте повторить позже
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может убрать из кучи половину камней, если количество камней в куче делится на два, иначе убрать из кучи два камня или убрать из кучи две трети камней, если количество камней в куче делится на три, иначе убрать из кучи три камня. Например, пусть в куче будет камней. Тогда за один ход можно получить кучу из или камней. Игра завершается в тот момент, когда количество камней в куче становится меньше или равно
Победителем считается игрок, сделавший последний ход, то есть первым получивший позицию, в которой в куче будет и менее камней. В начальный момент в куче было камней .
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от игры противника.
Найдите максимальное значение при котором Ваня может выиграть своим первым ходом после неудачного хода Пети, который мог выиграть своим первым ходом.
Решение руками
Рассмотрим Первым ходом Петя делает неудачный ход в после чего Ваня убирает из кучи две трети камней, создавая этим позицию и побеждая.
Решение программой
from functools import lru_cache def moves(heap): m = [] if heap % 2 == 0: m += [heap // 2] else: if heap > 1: m += [heap - 2] if heap % 3 == 0: m += [heap // 3] else: if heap > 2: m += [heap - 3] return m @lru_cache(None) def game(heap): if heap <= 2: return 0 steps = [game(x) for x in moves(heap)] if any(x % 2 == 0 for x in steps): return min(x for x in steps if x % 2 == 0) + 1 return max(steps) + 1 for s in range(3, 100): print(s, game(s), [game(x) for x in moves(s)])
Ошибка.
Попробуйте повторить позже
Для игры, описанной в задании , найдите значение , при котором у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, но у Вани нет стратегии, которая позволяла бы ему гарантированно выиграть первым ходом.
from functools import lru_cache def moves(h): k = h[0] m = h[1] if m == 0: return (k + 1, 1), (k + 2, 2), (k * 3, 3) if m == 1: return (k + 2, 2), (k * 3, 3) if m == 2: return (k + 1, 1), (k * 3, 3) if m == 3: return (k + 1, 1), (k + 2, 2) @lru_cache(None) def f(h): if h[0] >= 43: return ’END’ if any(f(x) == ’END’ for x in moves(h)): return ’WIN1’ if all(f(x) == ’WIN1’ for x in moves(h)): return ’LOSE1’ if any(f(x) == ’LOSE1’ for x in moves(h)): return ’WIN2’ if all(f(x) == ’WIN1’ or f(x) == ’WIN2’ for x in moves(h)): return ’LOSE2’ for i in range(1, 43): h = i, 0 if f(h) == ’LOSE2’: print(i)
Ошибка.
Попробуйте повторить позже
Для игры, описанной в задании , существует несколько таких значений , при которых у Пети есть выигрышная стратегия, причём Петя не может выиграть первым ходом, но может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найдите наименьшее и наибольшее из таких значений . В ответе, через пробел, запишите сначала наименьшее, затем наибольшее значение.
from functools import lru_cache def moves(h): k = h[0] m = h[1] if m == 0: return (k + 1, 1), (k + 2, 2), (k * 3, 3) if m == 1: return (k + 2, 2), (k * 3, 3) if m == 2: return (k + 1, 1), (k * 3, 3) if m == 3: return (k + 1, 1), (k + 2, 2) @lru_cache(None) def f(h): if h[0] >= 43: return ’END’ if any(f(x) == ’END’ for x in moves(h)): return ’WIN1’ if all(f(x) == ’WIN1’ for x in moves(h)): return ’LOSE1’ if any(f(x) == ’LOSE1’ for x in moves(h)): return ’WIN2’ minim = 10000 maxim = 0 for i in range(1, 43): h = i, 0 if f(h) == ’WIN2’: minim = min(minim, i) maxim = max(maxim, i) print(minim,maxim)
Ошибка.
Попробуйте повторить позже
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень, добавить два камня или увеличить количество камней в куче в три раза. При этом нельзя повторять ход, который только что сделал второй игрок.
Например, если в начале игры в куче камня, Петя может первым ходом получить кучу из или камней. Если Петя получил кучу из камней (добавил камня), то следующим ходом Ваня может получить или камней. Получить камней Ваня не может, так как для этого нужно добавить камня, а такой ход только что сделал Петя.
Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается, когда количество камней в куче становится не менее . Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет или больше камней.
В начальный момент в куче было камней,
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Укажите такое значение при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
from functools import lru_cache def moves(h): k = h[0] m = h[1] if m == 0: return (k + 1, 1), (k + 2, 2), (k * 3, 3) if m == 1: return (k + 2, 2), (k * 3, 3) if m == 2: return (k + 1, 1), (k * 3, 3) if m == 3: return (k + 1, 1), (k + 2, 2) @lru_cache(None) def f(h): if h[0] >= 43: return ’END’ if any(f(x) == ’END’ for x in moves(h)): return ’WIN1’ if all(f(x) == ’WIN1’ for x in moves(h)): return ’LOSE1’ for i in range(1, 43): h = i, 0 if f(h) == ’LOSE1’: print(i)
Ошибка.
Попробуйте повторить позже
Найдите количество значений S, при которых одновременно выполняются два условия:
— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
def moves(h): ans = [] if (h+1) % 2 == 1: ans.append(h+1) if (h+3) % 2 == 1: ans.append(h+3) if (h*3) % 2 == 1: ans.append(h*3) return ans def f(h): if h >= 51: return ’END’ if any(f(x) == ’END’ for x in moves(h)): return ’P1’ if all(f(x) == ’P1’ for x in moves(h)): return ’V1’ if any(f(x) == ’V1’ for x in moves(h)): return ’P2’ if all(f(x) == ’P2’ for x in moves(h)): return ’V2’ count = 0 for i in range(1, 51): if f(i) == ’V2’: count += 1 print(count)
Ошибка.
Попробуйте повторить позже
Найдите два наибольших значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
— Петя не может выиграть за один ход;
— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.
def moves(h): ans = [] if (h+1) % 2 == 1: ans.append(h+1) if (h+3) % 2 == 1: ans.append(h+3) if (h*3) % 2 == 1: ans.append(h*3) return ans def f(h): if h >= 51: return ’END’ if any(f(x) == ’END’ for x in moves(h)): return ’P1’ if all(f(x) == ’P1’ for x in moves(h)): return ’V1’ if any(f(x) == ’V1’ for x in moves(h)): return ’P2’ predmax = 0 maxim = 0 for i in range(1, 51): if f(i) == ’P2’: predmax = maxim maxim = i print(predmax, maxim)
Ошибка.
Попробуйте повторить позже
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может увеличить количество камней в куче в три раза, добавить в кучу один камень, или 3 камня, при этом после каждого хода в куче должно быть нечетное количество камней. Например, пусть в куче было 8 камней. Тогда за один ход можно получить кучу из 9 камней или из 11 камней (увеличить количество камней в три раза нельзя, т.к. после этого хода получится четное количество камней – 24). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 51.
В начальный момент в куче было S камней; . Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Ответьте на следующие вопросы:
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Назовите минимальное значение S, при котором это возможно. При этом, если у Пети существует всего 1 возможный ход, который приводит Ваню к победе, то такая позиция не считается. Другими словами — единственный возможный ход нельзя назвать неудачным.
def moves(h): ans = [] if (h+1) % 2 == 1: ans.append(h+1) if (h+3) % 2 == 1: ans.append(h+3) if (h*3) % 2 == 1: ans.append(h*3) return ans def f(h): if h >= 51: return ’END’ if any(f(x) == ’END’ for x in moves(h)): return ’P1’ if any(f(x) == ’P1’ for x in moves(h)) and len(moves(h)) >= 2: return ’V1’ for i in range(1, 51): if f(i) == ’V1’: print(i) break
Ошибка.
Попробуйте повторить позже
Найдите два минимальных значения , при которых у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, и при этом у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Найденные значения запишите в ответе в порядке возрастания через пробел.
# c = 1 если в прошлый ход меняли кучи местами
def moves(h):
a, b, c = h
res = []
res.append((a, b * 2, 0))
if c == 0:
res.append((b, a, 1))
return tuple(res)
@lru_cache(None)
def f(h):
if sum(h[:2]) >= 199:
return "END"
if any((f(x) == "END") for x in moves(h)):
return "P1"
if all((f(x) == "P1") for x in moves(h)):
return "V1"
if any((f(x) == "V1") for x in moves(h)):
return "P2"
if all((f(x) == "P2" or f(x) == "P1") for x in moves(h)):
return "V2"
for s in range(1, 100):
h = 99, s, 0
if f(h) == "V2":
print(s, "V2")
Ошибка.
Попробуйте повторить позже
Укажите минимальное значение , при котором у Пети есть выигрышная стратегия, причём Петя не может выиграть первым ходом, но может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
# c = 1 если в прошлый ход меняли кучи местами
def moves(h):
a, b, c = h
res = []
res.append((a, b * 2, 0))
if c == 0:
res.append((b, a, 1))
return tuple(res)
@lru_cache(None)
def f(h):
if sum(h[:2]) >= 199:
return "END"
if any((f(x) == "END") for x in moves(h)):
return "P1"
if all((f(x) == "P1") for x in moves(h)):
return "V1"
if any((f(x) == "V1") for x in moves(h)):
return "P2"
if all((f(x) == "P2" or f(x) == "P1") for x in moves(h)):
return "V2"
for s in range(1, 100):
h = 99, s, 0
if f(h) == "P2":
print(s, "P2")
Ошибка.
Попробуйте повторить позже
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может увеличить количество камней во второй куче в два раза или поменять кучи местами. Второй раз менять кучи, если это уже сделал противник, нельзя. Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее . Победителем считается игрок, сделавший последний ход, т. е. первым получивший позицию, в которой в кучах будет или больше камней.
В начальный момент в первой куче было камней, во второй куче — камней, . Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Назовите минимальное значение , при котором это возможно.
from functools import lru_cache # c = 1 если в прошлый ход меняли кучи местами def moves(h): a, b, c = h res = [] res.append((a, b * 2, 0)) if c == 0: res.append((b, a, 1)) return tuple(res) @lru_cache(None) def f(h): if sum(h[:2]) >= 199: return "END" if any((f(x) == "END") for x in moves(h)): return "P1" if any((f(x) == "P1") for x in moves(h)): return "V1" for s in range(1, 100): h = 99, s, 0 if f(h) == "V1": print(s, "V1")