Условие: № 9842 Основная волна 27.06.23 (Уровень: Базовый)
• Статья подготовлена командой itpy, подписывайтесь на наш телеграм канал!
№ 9842 Основная волна 27.06.23 (Уровень: Базовый)
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один или три камня либо увеличить количество камней в куче в четыре раза. Для того, чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее 111.
Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, состоящую из 111 или более камней.
В начальный момент в куче было S камней; 1 ≤ S ≤ 110.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника.
Задание 19.
Укажите такое значение S, при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом.
Задание 20.
Для игры, описанной в задании 19, найдите два таких минимальных значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
− Петя не может выиграть за один ход;
− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания.
Задание 21.
Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:
– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Если найдено несколько значений S, в ответе запишите наименьшее из них.
Решение задачи №19:
Создание таблицы с вариантами хода:
Создадим маленькую таблицу, в которой будут находиться:
- Варианты хода игрока.
- Количество камней, необходимое для победы.
Структура основной таблицы:
Создадим основную таблицу для нашей игры. Обсудим ее структуру:
- 1 столбец - Косметический, включает в себя только номер задания, к которому относится таблица.
- 2 столбец - В нем нас интересует только одна ячейка, которая выделена желтым. (S куча) В эту ячейку мы будем класть значение, которое обозначает количество камней в начальный момент игры.
- 3 столбец - Ходы Пети.
- 4 столбец - Ходы Вани.
Записываем во вторую ячейку 2-го столбца абсолютно любое число.
Создание таблицы (столбец с ходами Пети):
Заполняем 3-й столбец, используя нашу табличку с вариантами хода:
- Нажимаем на ячейку F2, ставим знак “=”, выделяем ячейку E2 и делаем ход “+1”.
- Нажимаем на ячейку F3, ставим знак “=”, выделяем ячейку E2 и делаем ход “+3”.
- Нажимаем на ячейку F4, ставим знак “=”, выделяем ячейку E2 и делаем ход “*4”.
Условное форматирование (столбец с ходами Пети):
В условии сказано, что Петя не может выиграть первым ходом, а Ваня может выиграть своим первым ходом при любой игре Пети.
Поэтому если Петя получит кучу, содержащую ≥ 111 камней, то этот ход будет выделен красным.
В свою очередь если Ваня получит кучу, содержащую ≥ 111 камней, то этот ход будет выделен зеленым.
Нужно сделать заливку, которая будет отображать выполнение условия задачи (зеленый - удовлетворяет условию задачи, красный - противоречит ему). Выделяем 3-й столбец, заходим в меню “Условное форматирование”, заходим в меню “Правила выделения ячеек”, выбираем “Другие правила”.
В описании правила мы задаем следующие параметры.
Нажимаем на кнопку “Формат…”. В меню “Заливка” выбираем красный цвет, т.к. в условии сказано, что Петя не может выиграть своим первым ходом.
Создание таблицы (столбец с ходами Вани):
Перед тем как заполнять 4-й столбец, нужно понять, что Ваня хочет победить в игре, и чтобы как можно быстрее набрать нужное количество камней, ему нужно делать самый сильный ход из возможных. В нашем случае это ход “*4”.
Заполняем 4-й столбец, используя нашу табличку с вариантами хода:
- Нажимаем на ячейку G2, ставим знак “=”, выделяем ячейку F2 и делаем ход “*4”.
- Нажимаем на ячейку G3, ставим знак “=”, выделяем ячейку F3 и делаем ход “*4”.
- Нажимаем на ячейку G4, ставим знак “=”, выделяем ячейку F4 и делаем ход “*4”.
Условное форматирование (столбец с ходами Вани):
Все аналогично столбцу Пети, но заливку делаем зеленую, т.к. Ваня должен выиграть своим первым ходом.
Работа с таблицей:
Получаем готовую для работы таблицу.
Теперь нам нужно подобрать такое число в ячейке E2, чтобы все ячейки столбца G были с зеленой заливкой, но в то же время столбец F должен быть без ячеек с красной заливкой. Нам достаточно лишь поменять число в ячейке, чтобы изменились все ходы игроков.
Чем больше “зеленых” ячеек и чем ближе числа к нужному для победы значению, тем меньше делаем шаг.
Когда нам не будет хватать одной “зеленой” ячейки до победы, делаем шаг +1.
Если же наоборот, мы видим все “зеленые” ячейки и одну “красную”, делаем шаг -1.
Таким образом, при условии того, что в начальной куче лежит 27 камней:
- Петя не может выиграть своим первым ходом.
- Ваня гарантировано выигрывает при любой игре Пети.
Условие задачи выполнено. Записываем в ответ.
Ответ к заданию №19: 27
Решение задачи №20:
Структура основной таблицы:
Таблица для этого номера не будет иметь особых различий с предыдущей, разве что мы выделим еще один столбец для второго хода Пети. Стоит отметить, что визуально таблица будет казаться большой, но благодаря условному форматированию нам нужно лишь менять значение S кучи до того момента, пока все нужные нам ячейки не станут “зелеными”. В конечном счете, наша структура выглядит так:
- 1 столбец - Косметический, включает в себя только номер задания, к которому относится таблица.
- 2 столбец - S куча.
- 3 столбец - Первый ход Пети.
- 4 столбец - Первый ход Вани.
- 5 столбец - Второй ход Пети.
Создание таблицы:
Заполняем таблицу точно так же как в №19.
Важно понимать, что на каждый ход Пети(”+1”, “+3”, “*4”) у Вани есть 3 хода(”+1”, “+3”, “*4”), а Петя в свою очередь на каждый ход Вани может ответить самым сильным ходом(”*4”).
Как мы видим, Петя на своем первом ходу сделал лишь один из трех возможных ходов, значит нам нужно прописать игры при двух других ходах. Иными словами, нам нужно создать еще две такие таблицы, и объединить их все в одну общую.
Создаем общую таблицу:
Тоже самое делаем для первого хода Пети “*4”.
Как итог, мы получаем таблицу, в которой содержатся все возможные варианты ходов игроков. Впоследствии, маленькие таблички, которые составляет нашу общую, я буду называть “блоками”. Их у нас 3шт., каждый ограничен жирными границами имеет размер в 3 строчки.
Условное форматирование в №20 нам ни к чему, ведь мы уже сделали его в предыдущем задании.
Даже при условии того, что мы просто скопировали таблицу из №19, выполнение/нарушение условия будет отображаться как надо.
(На картинке видно, как Петя побеждает вторым ходом и ячейка становится “зеленой”).
Работа c таблицей:
В условии нас интересует, что Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Это значит, что в хотя бы в одном из блоков должно быть 3 “зеленых” ячейки после второго хода Пети и ни одной “красной” ячейки после хода Вани.
Число 24 нас полностью устраивает, ведь при нем мы имеем 3 “зеленых” ячейки и 0 “красных” во втором блоке. Записываем в ответ и двигаемся дальше. Мы остановились на числе 25, значит возьмем число 26.
Число 26 тоже нас устраивает, т.к. при нем мы имеем 3 “зеленых” ячейки и 0 “красных” в первом блоке. Записываем в ответ.
Ответ к заданию №20: 24 26
Решение задачи №21:
Структура основной таблицы:
Таблица для №21 - это 3 таблицы №20. Действуем по аналогии с предыдущей таблицей, только на этот раз мы добавим столбец для второго хода Вани. Структура выглядит следующим образом:
- 2 столбец - 1 столбец - Косметический, включает в себя только номер задания, к которому относится таблица.
- 2 столбец - S куча.
- 3 столбец - Первый ход Пети.
- 4 столбец - Первый ход Вани.
- 5 столбец - Второй ход Пети.
- 6 столбец - Второй ход Вани.
Создание таблицы:
Делаем точно так же для остальных ходов Пети. Получаем общую таблицу, которая будет состоять так же из 3-х блоков, но блоки уже размеров в 9 строчек и содержат 3 маленьких “подблока” по 3 строчки (блок из №20).
Выглядит страшно, но алгоритм решения все так же прост: нам нужно подобрать такие значения S кучи, чтобы нужные нам ячейки стали “зелеными”.
Условное форматирование:
В этом задании нам нужно будет внести некоторые поправки. Обратимся к условию, где нам сказано:
- У Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети.
- У Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Первое условие можно воспринимать как: “В каждом блоке должен быть хотя бы один подблок с 3-мя “зелеными” ячейками после второго хода Вани”. А вот на втором условии следует заострить внимание. Его мы интерпретируем как: “ “синяя” ячейка не должна быть в каждом блоке после первого хода Вани”.
Сделаем синюю заливку для первого столбца Вани.
Работа с таблицей:
При значении 23 наше условие удовлетворяется во всех блоках, а именно:
- В 1-м блоке Ваня побеждает во второй ход во втором подблоке.
- В 2-м блоке Ваня побеждает во второй ход во втором подблоке.
- В 3-м блоке Ваня побеждает в первый ход в третьем подблоке.
Записываем в ответ.
