Все для самостоятельной подготовки к ЕГЭ
Зарегистрироваться

Бесплатный интенсив по информатике

27 марта — 3 апреля

На бесплатном интенсиве ты:
📍Узнаешь как и зачем Петя и Витя играют в камни.
📍Научишься предугадывать шаги соперника и правильно решать задачу.
📍Попробуешь решить эти задания разными способами.
📍Рассмотришь разные варинты Теории Игр.

Два игрока, Коля и Саша, играют в следующую игру. Перед игроками лежат две кучи…

Разбор сложных заданий в тг-канале:

Два игрока, Коля и Саша, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Коля. За один ход игрок может добавить в одну из куч (по своему выбору) два камня или увеличить количество камней в куче в два раза. Например, пусть в одной куче 15 камней, а в другой - 20 камней; такую позицию будем обозначать (15; 20). Тогда за один ход можно получить любую из четырёх позиций (17; 20), (15; 22), (30; 20), (15; 40). У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.

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

Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока - значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. Например, при начальных позициях (54; 3), (40; 30), (50; 15) выигрышная стратегия есть у Коли. Чтобы выиграть, ему достаточно удвоить количество камней в первой куче.

Выполните следующие задания.

Задание 1. Для каждой из начальных позиций (15; 47), (44; 20) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.

Задание 2. Для каждой из начальных позиций (15; 45), (13; 47), (42; 20) укажите, кто из игроков имеет выигрышную стратегию. В каждом случае опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии.

Задание 3. Для начальной позиции (13; 45) укажите, кто из игроков имеет выигрышную стратегию. Опишите выигрышную стратегию; объясните, почему эта стратегия ведёт к выигрышу, и укажите, какое наибольшее количество ходов может потребоваться победителю для выигрыша при этой стратегии. Постройте дерево всех партий, возможных при указанной вами выигрышной стратегии. Представьте дерево в виде рисунка или таблицы.

Объект авторского права ООО «Легион»

Посмотреть решение

Вместе с этой задачей также решают:

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

В Высшей Школе Экологии на факультете Экологии K бюджетных мест. N абитуриентов подали документы на этот факультет. Определить проходной балл на факультете. Проходной балл - количе…

Для хранения растрового изображения, содержащего только чёрный и белый цвета, использовали текстовый файл, в котором сохранили позиции пикселей белого цвета. Было решено частично и…

По результатам прошедшей олимпиады Google Code Jam участников награждают дипломами I, II и III степени. Если несколько участников набрали одинаковое количество баллов, они получают…