Ошибка.
Попробуйте повторить позже
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч один камень или увеличить количество камней в куче в три раза. Чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 49. Победителем считается игрок, сделавший последний ход, т. е. первым получивший позицию, в которой в кучах будет 49 или больше камней.
В начальный момент в первой куче было 5 камней, во второй куче - S камней, 1 < S < 43. Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Назовите минимальное значение S, при котором это возможно.
Решение "руками":
На бумаге:
Минимальное значение во второй куче, при котором игра завершается — 49-5=44. Максимальный ход, который мы имеем в игре — *3, следовательно, промежуток, при котором игрок побеждает одним ходом, располагается от 15 до 44.
Умножаем 15 на 3, получаем 45. Для того, чтобы оказаться в выигрышной позиции, нам нужно, чтобы значение камней во второй куче было равно минимум 49-45=4. Ответ — 4.
Excel:
Откройте Excel, в ячейке С1 введите "49 число выигрышных камней. Постройте таблицу для всех возможных ходов. В ячейке A5 записываем начальное количество камней в первой куче - "5". В ячейке B5 будем изменять количество камней. В ячейки C5:D8 вносим ходы Пети (+1 и *3): С5=A5+1, С6=A5, С7=A5*3, С8=A5, D5=B5, D6=B5+1, D7=B5, D8=B5*3.
В ячейках E5:E8 формируем ходы Вани. Задача Вани - максимизировать количество камней в куче для ускорения победы. Оптимальный ход - умножить на 3 кучу с большим количеством камней и добавить вторую. Поэтому E5=MAX(C5:D5)*3+MIN(C5:D5).
Для удобства отслеживания победных ходов используем условное форматирование. Выделяем ячейку E5, переходим в "Условное форматирование "Правила выделения ячеек "другие правила и применяем правило подсветки ячейки зеленым при условии победы.
Протянем ячейку Е5 c формулой и форматированием до ячейки Е8.
Теперь в ячейку B5 можно вводить различные значения и анализировать возможные исходы игры. Заметим, при B5=4, у нас впервые «загорается» одна ячейка зеленым – это означает выигрыш. Петя создает кучу (15,4) – совершает неудачный ход, что приводит к победе Вора, формирующего выигрышную комбинацию с суммой 49.
Решение с помощью программы:
from functools import lru_cache @lru_cache(maxsize=None) def f(n,m) : if n+m >= 49 : return 0 s = [f(n+1,m), f(n*3,m), f(n,m+1), f(n,m*3)] t = [x for x in s if x <= 0] if t : return -max(t) + 1 else : return -max(s) res = set() for s in range(1, 49 + 1) : if f(5 + 1, s) == 1 : res.add(s) if f(5 * 3, s) == 1 : res.add(s) if f(5, s + 1) == 1 : res.add(s) if f(5, s * 3) == 1 : res.add(s) print(min(res))
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное обучение
в Школково
Для детей ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Брянской областей, а также школьникам, находящимся в пунктах временного размещения Крыма обучение на платформе бесплатное.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ или олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
