Всем доброго времени суток с вами Иван Викторович это разбор заданий 192021 демо версии ЕГ по информатике проект 2025 года начнём мы с вами с задание девятнадцатого Это задание базового уровня и Согласно спецификации пино выполнение отводится 6 минут Это задание проверяет ваше умение анализировать алгоритм логической игры Итак у нас есть два игрока Пет и Ваня они играют следующую игру перед ними лежит куча камней игроки ходят по очереди первый ход делает Петя за один ход игрок может убрать из кучи два камня или убрать из кучи пять камней или уменьшить количество камней в куче в три раза при этом количество камней полученное при делени округляется до меньшего игра завершается когда количество камней в куче становится не более девятнадцати Ну и победителем считается игрок сделавший последний ход то есть первым получивший кучу в которой будет 19 или меньше камней в начальный момент в куче было S камней S больше либо равно 20 Укажите минимальное значение S при котором Петя не может выиграть за один ход но при любом ходе Пети Ваня может выиграть своим первым ходом давайте мы с вами напишем очень примитивную рекурсивную функцию и спокойно справимся при помощи этой функции и с девятнадцатым и с двадцатым и с двадцать первым заданием Итак поехали я определяю функцию давайте я её назову F что мы ей пропишет это X это текущее количество камней то есть вот в данный момент и допустим переменная п это будет текущий ход всей игры и вот здесь внимание смотрите когда игра ещё не началась у нас P равно нулю Но когда у нас ходы Пети они всегда нечётные Почему пти ходит первым то есть у него будет ход первый третий пятый седьмой и так далее То есть его ходы в рамках всей игры всегда нечётный А у Вани наоборот всегда чётный почему Ну в ход всей игры четвёртый шестой восьмой и так далее на этом мы с вами и будем акцентировать внимание то есть получается Давайте пропиши следующее если у нас в куче Да в текущий момент меньше либо равно 19 камням то есть там 19 или менее камней или Мы с вами уже ушли за второй ход всей игры А я Напоминаю что второй ход всей игры - Это первый ход ва Нам же здесь нужно найти чтобы Ваня выиграл своим первым ходом поэтому его второй третий четвёртый пятый ход Вани ну нас просто-напросто не интересует Поэтому если у нас P больше двух то что мы делаем мы возвращаем следующую проверку результат проверки что сейчас реально первый ход Вани то есть второй ход всей игры мы это проверяем Да P сейчас равно двум или нет И здесь будет либо либо Ладненько А теперь давайте пропи ходы то есть смотрите если у нас хо сейчас получается допустим нечётный А нечётные ходы я напоминаю это всегда ходы Пети Это первый третий пятый и так далее да Если у вас там очень большая игра то что мы делаем мы соответственно ходим А как мы ходим мы Записываем следующее то есть мы вызываем нашу функцию и начинаем выполнять эти ходы какие у нас ходы Либо мы убираем два камня либо пять камней либо уменьшаем в три раза То есть я здесь вызываю X - 2 но мы сделали ход игрок наш сделал ход со это ход считаем Да у нас здесь счётчик ходов либо Почему я здесь ставлю или Ну потому что нам сказано что у Пети любая игра мы при любом ходе Пети поэтому Пети может делать что угодно и как угодно он может МИД Может -5 может делить на 3 пожалуйста мы это всё должны учитывать прописываем следующее у нас x - 5 и мы считаем этот ход либо у нас получается X де нацело на 3 при этом нам сказано что количество Каме получен округляется до меньшего простыми словами мы берём целую часть целую часть поэтому я пишу здесь два слэша Да целая часть отделени и также не забываем считать ход прекрасно но это у нас ходы Пети но у нас же ещё и Ваня естественно делает свои ходы А что он делает у него выигрышной стратегия он должен победить по-любому поэтому он делает только те ходы которые приносят ему побед поэтому здесь мы просто копируем весь этот большой РН вставляем ниже но or меняем на N Да Ване здесь нужны все единицы меняем на N всё то есть вот она получается выигрышная стратегия А Или это у нас получается любая игра всё наша рекурсивная функция готова и что мы делаем мы просто будем сейчас в цикле перебирать значение переменной S Мы же её не знаем да чему там была равна эта переменная Поэтому просто это переберёмся то есть смотрите при помощи генератора списка Я заполню этот список значением переменной S откуда я их беру я их возьму на диапазоне игроки смотрите здесь уменьшают они увеличивают количество камней в куче поэтому я начну перебор от большего Ну не знаю допустим от 100 до получается де Почему до де Почему Потому что нам сказано S больше либо равно 20 Вот это 19 не входит в диапазон здесь будет последнее число 20 Да если мы перебираем от большего к меньшему ну и соответственно шага -1 и При каком раскладе да При каком условии я эти переменной S закидываю в список если f от S нуля У нас вернёт True То есть это значит что Ваня победил своим первым ходом то есть мы передаём здесь это количество камней в исходный момент и указываем что это исходный момент это начало ещё ни один игрок не сделал свой ход всё спокойненько запускаем и получаем с вами два значения 61 и 60 Нам нужно в ответе указать минимальное значение поэтому ответ на девятнадцатое задание - это 60 но мы идём дальше д задание Это задание уже повышенного уровня и Согласно спецификации на выполнени отводится уже 8 минут и Это задание проверяет ваше умение найти выигрышную стратегию игры и что мы здесь видим что у нас здесь должно одновременно выполняться два условия Петя не может выиграть за один ход Петя может выиграть своим вторым ходом независимо от того как будет ходить Ваня то есть теперь нас интересует второй ход Пети второй ход Пети - это третий ход всей игры Первый ход Пети - Это первый ход всей игры Второй ход всей игры - Это первый ход Вани и третий ход всей игры - это второй ход Пети поэтому здесь я просто с двоечки меняю на троечку и нам даже не нужно ничего особо с вами переписывать здесь в принципе всё перебор оставляю без каких-либо изменений но немножечко поменяем теперь у нас получается любая игра у кого у Вани Да Независимо от того как будет ходить Вань поэтому здесь я меняю следующее То есть если у нас ход Какой чётный это значит ход Вани и у него любая игра Это всё что нужно вам было заменить и Вы спокойно эту же функцию Да этот же перебор немножко изменённую функцию Да вы запускаете и получаете ответ вам нужно Здесь в ответе указать что два наименьших значения в порядке возрастания То есть вы пишете 62 63 всё дца задание решено мы переходим к двадцать первому это уже задание высокого уровня Согласно спецификации но выполнения отводится уже 11 минут и Это задание проверяет ваше умение построить дерево игры по заданному алгоритму и найти выигрышную стратегию но мы не будем с вами ничего переписывать писать новый рекурсию или что-то ещё или новый перебор мы просто изменим существующую функцию смотрите здесь в двадцать первом задании что от нас хотят что у Вани есть выигрышная стратегия позволяющему выиграть первым или вторым ходом при любой игре ти и у Вани нет стратегии которая позволит ему гарантированно выиграть с первым ходом как это было в девятнадцатом номере Поэтому я здесь что ставлю у нас получается первый ход Вани - это второй ход всей игры Второй ход Вани - это четвёртый ход всей игры то есть мы с вами вот здесь вот меняем на четвёртом на четвёрочка либо сейчас первый ход Ване то есть второй ход всей игры либо соответственно сейчас второй ход Вани то есть четвёртый ход всей игры вот таким вот образом и смотрите Теперь у Пети любая игра А у Вани нет поэтому я здесь просто вот это вот удаляю и получается что если ход нечётный у нас любая игра если чётный то у нас с вами есть стратегия мы запускаем и получаем значение нам нужно указать в ответе минимальное значение переменно мы не торопимся и не пишем в ответе 60 почему Ну промотай немножечко это видео назад вспомните решение дего номера мы там получили что при первом ходе Ваня гарантированно выиграет если там будут значения 60 и 61 А нам здесь сказано что у него нет стратегии которая позволит ему гарантированно выиграть первым кодом поэтому здесь ответ будет минимальный 64 Вы можете это Элементарно проверить сейчас берёте и убираете второй ход Вани то есть четвёртый ход всей игры вот таким вот образом и вы видите что здесь будут эти значения 60 и 61 он при этих значениях гарантированно выиграет в первом А у нас здесь такой гарантии нет Да поэтому ещё раз что я делаю Я возвращаю запускаю И получаю 64 - это минимальное значение переменной S при котором одновременно выполняется два этих условия всё задание решено но вы не забудьте подписаться поставить лайк и да новых встреч пока