{"draftJsState":{"blocks":[{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Задание 19 ЕГЭ Информатика ФИПИ","type":"header-two","key":"bvs5r"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может","type":"unstyled","key":"1rslp"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":27,"offset":0,"style":"BOLD"},{"length":45,"offset":32,"style":"BOLD"}],"text":"добавить в кучу один камень или увеличить количество камней в куче в два раза.","type":"unstyled","key":"fe1gf"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Например, имея кучу из 10 камней, за один ход можно получить кучу из 11 или из 20 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.","type":"unstyled","key":"fjhr3"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Игра завершается в тот момент, когда количество камней в куче превышает 45. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 46 или больше камней.","type":"unstyled","key":"1gae"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":1,"offset":31,"style":"ITALIC"},{"length":1,"offset":45,"style":"ITALIC"}],"text":"В начальный момент в куче было S камней, 1 ≤ S ≤ 45.","type":"unstyled","key":"5tlp5"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":10,"offset":289,"style":"BOLD"}],"text":"Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока  — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы следующего стратегии игрока, которые не являются для него безусловно выигрышными.","type":"unstyled","key":"372vg"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":1,"offset":111,"style":"ITALIC"}],"text":"Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.","type":"unstyled","key":"ap0g"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Решение","type":"header-three","key":"ebb31"},{"data":{"image":{"id":"6901d59c63c154286427b90b"}},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Задание 19 ЕГЭ Информатика","type":"atomic:image","key":"5n2v2"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"1. Структура рекурсивной функции f(x, p)","type":"header-three","key":"a9vlf"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Функция f(x, p) проверяет, может ли игрок на текущем ходе выиграть при данных условиях.","type":"unstyled","key":"dro78"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":10,"offset":0,"style":"BOLD"}],"text":"Параметры:","type":"unstyled","key":"askms"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"x - текущее количество камней в куче","type":"unordered-list-item","key":"4v1ki"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"p - номер хода (0 - начало игры, 1 - первый ход, 2 - второй ход)","type":"unordered-list-item","key":"eqlpa"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"2. Базовые случаи (условия завершения)","type":"header-three","key":"5030b"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"if x >= 46 and p == 2:","type":"blockquote","key":"3i6p"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":" return 1","type":"blockquote","key":"qkou"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Если камней ≥46 И это второй ход (ход Вани) → Ваня выиграл → возвращаем 1 (победа)","type":"unstyled","key":"d0m09"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"elif x < 46 and p == 2:","type":"blockquote","key":"ef6g"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":" return 0","type":"blockquote","key":"f2bdq"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Если камней <46 И это второй ход → игра закончилась, но Ваня не выиграл → возвращаем 0 (проигрыш)","type":"unstyled","key":"duj67"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"elif x >= 46 and p < 2:","type":"blockquote","key":"9d61t"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":" return 0","type":"blockquote","key":"e2bjn"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Если камней ≥46 ДО второго хода → Петя выиграл на первом ходу → возвращаем 0 (это не удовлетворяет условию, что Ваня выиграл)","type":"unstyled","key":"3bd6k"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"3. Рекурсивные вызовы","type":"header-three","key":"88unr"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"else:","type":"blockquote","key":"3fi4n"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"a = []","type":"blockquote","key":"chfbv"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"a.append(f(x + 1, p + 1))","type":"blockquote","key":"9sh1i"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"a.append(f(x * 2, p + 1))","type":"blockquote","key":"crfg"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"return any(a)","type":"blockquote","key":"7rv91"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Если игра продолжается, рассматриваем все возможные ходы:\nДобавить 1 камень: f(x + 1, p + 1)\nУдвоить количество: f(x * 2, p + 1)","type":"unordered-list-item","key":"1nu65"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"any(a) возвращает True (1), если ХОТЯ БЫ ОДИН из ходов ведёт к победе","type":"unordered-list-item","key":"79gm6"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"4. Логика работы программы","type":"header-three","key":"fv8g6"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":12,"offset":0,"style":"BOLD"}],"text":"Цикл поиска:","type":"unstyled","key":"73t4"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"python","type":"unstyled","key":"82r0l"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"for s in range(1, 46):\n if f(s, 0) == 1:\n print(\"19 задание = \", s)\n break","type":"blockquote","key":"3os9h"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Перебираем все возможные начальные значения S от 1 до 45","type":"unordered-list-item","key":"4f95v"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Для каждого S запускаем функцию с параметрами f(s, 0) (начало игры, ход Пети)","type":"unordered-list-item","key":"8ut27"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Ищем минимальное S, при котором возвращается 1","type":"unordered-list-item","key":"86rrg"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"5. Как это соответствует условию задачи","type":"header-three","key":"3cqis"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Программа ищет ситуации, где:","type":"unstyled","key":"2r547"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Петя делает первый ход из позиции S","type":"ordered-list-item","key":"7r5bf"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Ваня выигрывает на своём первом ходу (p = 2)","type":"ordered-list-item","key":"dm6sb"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":6,"offset":0,"style":"BOLD"}],"text":"Важно: Функция проверяет, существует ли стратегия для текущего игрока, которая гарантирует победу при ЛЮБОМ ходе противника.","type":"unstyled","key":"2ktt7"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"6. Пример работы для S = 12","type":"header-two","key":"427in"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"f(12, 0):\n p=0, x=12 < 46\n Вычисляем f(13, 1) и f(24, 1)\n \n f(13, 1):\n p=1, x=13 < 46\n Вычисляем f(14, 2) и f(26, 2)\n \n f(14, 2): 14<46 и p=2 → return 0\n f(26, 2): 26<46 и p=2 → return 0\n any([0,0]) = 0\n \n f(24, 1):\n p=1, x=24 < 46\n Вычисляем f(25, 2) и f(48, 2)\n \n f(25, 2): 25<46 и p=2 → return 0\n f(48, 2): 48≥46 и p=2 → return 1\n any([0,1]) = 1\n \n any([0,1]) = 1","type":"blockquote","key":"f2sa9"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Результат: f(12, 0) = 1 → S=12 подходит.","type":"blockquote","key":"94qdo"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"7. Почему программа находит правильный ответ","type":"header-three","key":"b9ctq"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Программа проверяет для каждого S:","type":"unstyled","key":"cs8j1"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Может ли Петя выбрать такой ход, чтобы Ваня мог выиграть на своём ходе","type":"unordered-list-item","key":"9fppj"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"При этом учитываются ВСЕ возможные ответные ходы","type":"unordered-list-item","key":"6agge"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Функция возвращает 1, если существует ХОТЯ БЫ ОДИН ход Пети, приводящий к победе Вани.","type":"unstyled","key":"fcpsq"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"8. Особенности реализации","type":"header-three","key":"jadn"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"any() возвращает True при первом найденном True (ленивое вычисление)","type":"unordered-list-item","key":"ds1d6"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"break останавливает поиск после нахождения минимального подходящего S","type":"unordered-list-item","key":"2cefl"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Рекурсия может быть неэффективной для больших глубин, но здесь глубина всего 2 хода","type":"unordered-list-item","key":"6s7m7"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":21,"offset":0,"style":"BOLD"}],"text":"Результат выполнения: программа найдёт и выведет 19 задание = 12","type":"unstyled","key":"45bco"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Задача 20 ЕГЭ Информатика ФИПИ","type":"header-two","key":"bjpg0"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может","type":"unstyled","key":"3tqc"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":27,"offset":0,"style":"BOLD"},{"length":45,"offset":32,"style":"BOLD"}],"text":"добавить в кучу один камень или увеличить количество камней в куче в два раза.","type":"unstyled","key":"21tud"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Например, имея кучу из 10 камней, за один ход можно получить кучу из 11 или из 20 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.","type":"unstyled","key":"3a3a0"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Игра завершается в тот момент, когда количество камней в куче превышает 45. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 46 или больше камней.","type":"unstyled","key":"e2p2c"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":1,"offset":31,"style":"ITALIC"},{"length":1,"offset":45,"style":"ITALIC"}],"text":"В начальный момент в куче было S камней, 1 ≤ S ≤ 45.","type":"unstyled","key":"anur8"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":10,"offset":289,"style":"BOLD"}],"text":"Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока  — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы следующего стратегии игрока, которые не являются для него безусловно выигрышными.","type":"unstyled","key":"bsqe"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":1,"offset":27,"style":"ITALIC"}],"text":"Найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:","type":"unstyled","key":"erno0"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"—  Петя не может выиграть за один ход;","type":"unstyled","key":"n1t9"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"—  Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.","type":"unstyled","key":"8n6mm"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.","type":"unstyled","key":"c7rrm"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Решение","type":"header-two","key":"ak181"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":47,"offset":0,"style":"BOLD"}],"text":"1. Логика задачи в терминах рекурсивной функции","type":"header-two","key":"fr2vk"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":9,"offset":42,"style":"BOLD"},{"length":14,"offset":90,"style":"BOLD"}],"text":"Функция f(x, p) проверяет, может ли игрок при ходе p и количестве камней x достичь победы при своей игре в соответствии с условиями.","type":"unstyled","key":"8jvck"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":13,"offset":0,"style":"BOLD"}],"text":"p — чётность:","type":"unstyled","key":"236k9"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"p = 0 — ход Пети (начало)","type":"unordered-list-item","key":"2d6l3"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"p = 1 — ход Вани","type":"unordered-list-item","key":"dbinp"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"p = 2 — ход Пети (второй)","type":"unordered-list-item","key":"3togf"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"p = 3 — ход Вани (второй) — но игра может закончиться раньше.","type":"unordered-list-item","key":"209en"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"unstyled","key":"43koc"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"python","type":"header-three","key":"dg69l"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":26,"offset":199,"style":"ITALIC"},{"length":51,"offset":329,"style":"ITALIC"},{"length":27,"offset":407,"style":"ITALIC"},{"length":55,"offset":538,"style":"ITALIC"}],"text":"def f(x, p):\n if x >= 46 and p == 3: \n return 1\n elif x < 46 and p == 3: \n return 0\n elif x >= 46 and p < 3: \n return 0\n else:\n a = []\n if p % 2 != 0: # ход Вани (нечётные p: 1)\n a.append(f(x + 1, p + 1))\n a.append(f(x * 2, p + 1))\n return all(a) # Ваня выигрывает, если все его ходы ведут к победе\n else: # ход Пети (чётные p: 0, 2)\n a.append(f(x + 1, p + 1))\n a.append(f(x * 2, p + 1))\n return any(a) # Петя выигрывает, если хотя бы один ход ведёт к победе","type":"unstyled","key":"2ppuh"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":27,"offset":0,"style":"BOLD"}],"text":"2. Разбор условий в функции","type":"header-two","key":"hmm5"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Анализ работы программы для s = 11","type":"header-three","key":"1hfg2"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":15,"offset":0,"style":"BOLD"}],"text":"Логика функции:","type":"unstyled","key":"c920d"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"p - номер хода (0, 1, 2, 3)","type":"unordered-list-item","key":"3b6ol"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"p = 0, 2 (четные) - ходы противника: any (достаточно одного выигрышного пути)","type":"unordered-list-item","key":"fnr3u"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"p = 1, 3 (нечетные) - ходы нашего игрока: all (нужны все выигрышные пути)","type":"unordered-list-item","key":"dcb74"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Цель: на p = 3 иметь x ≥ 46","type":"unordered-list-item","key":"3fgmq"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":11,"offset":0,"style":"BOLD"},{"length":1,"offset":19,"style":"BOLD"}],"text":"Вычисление f(11, 0):","type":"unstyled","key":"b992k"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"f(11,0) → any\n├── f(12,1) → all → ❌ [0]\n│ ├── f(13,2) → any → ❌ [0]\n│ │ ├── f(14,3) → 0 (14<46)\n│ │ └── f(26,3) → 0 (26<46)\n│ └── f(24,2) → any → ✅ [1]\n│ ├── f(25,3) → 0 (25<46)\n│ └── f(48,3) → 1 (48≥46)\n└── f(22,1) → all → ✅ [1]\n ├── f(23,2) → any → ✅ [1]\n │ ├── f(24,3) → 0 (24<46)\n │ └── f(46,3) → 1 (46≥46)\n └── f(44,2) → any → ✅ [1]\n ├── f(45,3) → 0 (45<46)\n └── f(88,3) → 1 (88≥46)","type":"unstyled","key":"6b787"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":10,"offset":0,"style":"BOLD"}],"text":"Результат: f(11,0) = any([0, 1]) = 1 ✅","type":"unstyled","key":"fe2sd"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":21,"offset":0,"style":"BOLD"}],"text":"Выигрышная стратегия:","type":"unstyled","key":"1hjdv"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":5,"offset":0,"style":"BOLD"}],"text":"Ход 1 (p=0): 11 → 22 (умножить на 2)","type":"ordered-list-item","key":"bo60a"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":5,"offset":0,"style":"BOLD"}],"text":"Ход 2 (p=1): противник может пойти:\n22 → 23 (+1) → наш ответ: 23 → 46 (×2)\n22 → 44 (×2) → наш ответ: 44 → 88 (×2)","type":"ordered-list-item","key":"fmhb8"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Оба варианта гарантируют победу на 3-м ходу.","type":"unstyled","key":"14tue"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Анализ работы программы для s = 21","type":"header-three","key":"4je1d"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":15,"offset":0,"style":"BOLD"}],"text":"Логика функции:","type":"unstyled","key":"c7iu7"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"p - номер хода (0, 1, 2, 3)","type":"unordered-list-item","key":"2qvut"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"p = 0, 2 (четные) - ходы противника: any (достаточно одного выигрышного пути)","type":"unordered-list-item","key":"4lje3"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"p = 1, 3 (нечетные) - ходы нашего игрока: all (нужны все выигрышные пути)","type":"unordered-list-item","key":"6nur2"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Цель: на p = 3 иметь x ≥ 46","type":"unordered-list-item","key":"142k8"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":11,"offset":0,"style":"BOLD"},{"length":1,"offset":19,"style":"BOLD"}],"text":"Вычисление f(21, 0):","type":"unstyled","key":"dci2h"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"f(21,0) → any\n├── f(22,1) → all → ✅ [1]\n│ ├── f(23,2) → any → ✅ [1]\n│ │ ├── f(24,3) → 0 (24<46)\n│ │ └── f(46,3) → 1 (46≥46)\n│ └── f(44,2) → any → ✅ [1]\n│ ├── f(45,3) → 0 (45<46)\n│ └── f(88,3) → 1 (88≥46)\n└── f(42,1) → all → ❌ [0]\n ├── f(43,2) → any → ❌ [0]\n │ ├── f(44,3) → 0 (44<46)\n │ └── f(86,3) → 1 (86≥46)\n └── f(84,2) → any → ✅ [1]\n ├── f(85,3) → 1 (85≥46)\n └── f(168,3) → 1 (168≥46)","type":"unstyled","key":"d366j"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":10,"offset":0,"style":"BOLD"}],"text":"Результат: f(21,0) = any([1, 0]) = 1 ✅","type":"unstyled","key":"8ucan"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":21,"offset":0,"style":"BOLD"}],"text":"Выигрышная стратегия:","type":"unstyled","key":"5p8r2"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":5,"offset":0,"style":"BOLD"}],"text":"Ход 1 (p=0): 21 → 22 (+1)","type":"ordered-list-item","key":"8ues2"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":5,"offset":0,"style":"BOLD"}],"text":"Ход 2 (p=1): противник может пойти:\n22 → 23 (+1) → наш ответ: 23 → 46 (×2)\n22 → 44 (×2) → наш ответ: 44 → 88 (×2)","type":"ordered-list-item","key":"1olg1"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Оба варианта гарантируют победу на 3-м ходу.","type":"unstyled","key":"fn7it"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":26,"offset":0,"style":"BOLD"}],"text":"Ключевая логика ветвления:","type":"header-three","key":"b9dms"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Если p нечётное (Ваня), то all(a) — Ваня выигрывает, только если при любых его ходах (в рамках ограничения p=3) он побеждает.","type":"unordered-list-item","key":"ailj4"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Если p чётное (Петя), то any(a) — Петя выигрывает, если существует ход, ведущий к победе.","type":"unordered-list-item","key":"79it8"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Но из-за условия if x>=46 and p<3: return 0 — если Петя выигрывает на p=0 или p=2, это не считается? Нет, это условие говорит: если куча >=46 до p=3, то это не та ситуация, которую мы рассматриваем как \"успех по плану до p=3\". Это ошибка — оно должно быть return 1, если это ход Пети (p чётное), и return 0, если ход Вани (p нечётное), но у вас оно всегда 0.","type":"unstyled","key":"bn5v"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Задание 21 ЕГЭ Информатика ФИПИ","type":"header-two","key":"728sn"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может","type":"unstyled","key":"fv59n"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":27,"offset":0,"style":"BOLD"},{"length":45,"offset":32,"style":"BOLD"}],"text":"добавить в кучу один камень или увеличить количество камней в куче в два раза.","type":"unstyled","key":"4r9uf"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Например, имея кучу из 10 камней, за один ход можно получить кучу из 11 или из 20 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.","type":"unstyled","key":"27n8"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Игра завершается в тот момент, когда количество камней в куче превышает 45. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 46 или больше камней.","type":"unstyled","key":"cvnnd"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":1,"offset":31,"style":"ITALIC"},{"length":1,"offset":45,"style":"ITALIC"}],"text":"В начальный момент в куче было S камней; 1 ≤ S ≤ 45.","type":"unstyled","key":"af31e"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":10,"offset":289,"style":"BOLD"}],"text":"Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока  — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы следующего стратегии игрока, которые не являются для него безусловно выигрышными.","type":"unstyled","key":"33ad4"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":1,"offset":29,"style":"ITALIC"}],"text":"Найдите минимальное значение S, при котором одновременно выполняются два условия:","type":"unstyled","key":"2dsnl"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"—  у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;","type":"unstyled","key":"4ce3u"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"—  у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.","type":"unstyled","key":"c69a9"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Решение","type":"header-three","key":"9m1f8"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"def f(x,p):\n if x>=46 and (p==2 or p==4): return 1\n elif x<46 and p==4: return 0\n elif x>=46 and p<4:return 0\n else:\n a=[]\n if p%2==0:\n a.append(f(x+1,p+1))\n a.append(f(x*2,p+1))\n return all(a)\n else:\n a.append(f(x + 1, p + 1))\n a.append(f(x * 2, p + 1))\n return any(a)\nfor s in range(1,46):\n if f(s,0)==1:\n print(\"21 задание = \",s)","type":"unstyled","key":"5hchh"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"1. Понимание условия","type":"header-two","key":"3l900"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"У нас есть:","type":"unstyled","key":"61sds"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":4,"offset":0,"style":"BOLD"},{"length":4,"offset":17,"style":"BOLD"}],"text":"Петя (1-й ход) и Ваня ходят по очереди","type":"unordered-list-item","key":"1lrvo"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Начальное число: s (ищем, для каких s выигрывает Ваня)","type":"unordered-list-item","key":"37rtq"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Ход: +1 или *2","type":"unordered-list-item","key":"72np2"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":18,"offset":6,"style":"BOLD"}],"text":"Цель: первым достичь ≥46","type":"unordered-list-item","key":"92tlj"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":12,"offset":28,"style":"BOLD"}],"text":"Рассматриваются партии, где ровно 4 хода (2 хода Петей, 2 ходя Ваней)","type":"unordered-list-item","key":"9ut80"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"2. Анализ функции f(x, p)","type":"header-two","key":"59mj0"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Параметры:","type":"unstyled","key":"bkfiu"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"x — текущее число","type":"unordered-list-item","key":"1510f"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"p — номер хода (0, 1, 2, 3, 4)","type":"unordered-list-item","key":"745m9"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Условия:","type":"unstyled","key":"fjs53"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"python","type":"unstyled","key":"arerg"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"if x>=46 and (p==2 or p==4): return 1","type":"unstyled","key":"e63u1"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":6,"offset":21,"style":"BOLD"},{"length":6,"offset":50,"style":"BOLD"}],"text":"Если достигли 46+ на ходу 2 (первый ход Вани) или ходу 4 (второй ход Вани) — это победа Вани.","type":"unstyled","key":"e6lmp"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"python","type":"unstyled","key":"2aits"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"elif x<46 and p==4: return 0","type":"unstyled","key":"7f1iv"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Если после 4 ходов не достигли 46 — Ваня не выиграл.","type":"unstyled","key":"401n8"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"python","type":"unstyled","key":"a20bf"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"elif x>=46 and p<4: return 0","type":"unstyled","key":"43coj"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Если достигли 46+ до хода 2 или 4 — победа не в нужный момент (не Ваня выиграл).","type":"unstyled","key":"clri0"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"3. Логика ходов","type":"header-two","key":"bua8k"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":18,"offset":0,"style":"BOLD"}],"text":"p чётное (0, 2, 4) — ход Вани? Нет: p=0 — Петя, p=1 — Ваня, p=2 — Петя, p=3 — Ваня, p=4 — Петя? Подождите, проверяем:\np=0: Петя\np=1: Ваня\np=2: Петя\np=3: Ваня\np=4: Петя","type":"unordered-list-item","key":"dcvu"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Значит:","type":"unstyled","key":"57dkb"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":4,"offset":25,"style":"BOLD"}],"text":"p чётное (0, 2, 4) — ход Пети","type":"unordered-list-item","key":"68q8a"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":4,"offset":24,"style":"BOLD"}],"text":"p нечётное (1, 3) — ход Вани","type":"unordered-list-item","key":"96r83"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Дерево вычислений для f(20, 0) ✅❌","type":"header-two","key":"42lpq"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"f(20,0) = any ✅\n├── f(21,1) = all ❌\n│ ├── f(22,2) = any ❌\n│ │ ├── f(23,3) = all ❌\n│ │ │ ├── f(24,4) = 0 ❌\n│ │ │ └── f(46,4) = 1 ✅\n│ │ └── f(44,3) = all ❌\n│ │ ├── f(45,4) = 0 ❌\n│ │ └── f(88,4) = 1 ✅\n│ └── f(42,2) = any ✅\n│ ├── f(43,3) = all ❌\n│ │ ├── f(44,4) = 0 ❌\n│ │ └── f(86,4) = 1 ✅\n│ └── f(84,3) = all ✅\n│ ├── f(85,4) = 1 ✅\n│ └── f(168,4) = 1 ✅\n└── f(40,1) = all ✅\n ├── f(41,2) = any ✅\n │ ├── f(42,3) = all ❌\n │ │ ├── f(43,4) = 0 ❌\n │ │ └── f(84,4) = 1 ✅\n │ └── f(82,3) = all ✅\n │ ├── f(83,4) = 1 ✅\n │ └── f(164,4) = 1 ✅\n └── f(80,2) = 1 ✅","type":"unstyled","key":"1hktf"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":33,"offset":0,"style":"BOLD"}],"text":"Финальный результат: f(20, 0) = 1 ✅","type":"unstyled","key":"dco3h"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":60,"offset":0,"style":"BOLD"}],"text":"Присоединяйтесь к нашему каналу в ДЗЕН «Учитель версии 4.0»!","type":"header-three","key":"e1bq1"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Будем рады видеть вас среди наших подписчиков. На канале вас ждет эксклюзивный контент:","type":"unstyled","key":"79ojo"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Разборы сложных задач по Информатике.","type":"unordered-list-item","key":"2t5mn"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Советы по использованию Digital-инструментов в учебе.","type":"unordered-list-item","key":"5r6q8"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"Актуальные новости из мира образовательных технологий.","type":"unordered-list-item","key":"fenu9"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":35,"offset":0,"style":"BOLD"}],"text":"Подписывайтесь, чтобы быть в курсе!","type":"unstyled","key":"8j6au"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[{"length":19,"offset":0,"style":"ITALIC"},{"length":30,"offset":20,"style":"ITALIC"}],"text":"Учитель Информатики\nХалтурина Надежда Вячеславовна","type":"unstyled","key":"euld5"},{"data":{"image":{"id":"6901e08f63c1542864359e18"}},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"atomic:image","key":"cagjf"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"unstyled","key":"a0iqp"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"unstyled","key":"64sm9"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"unstyled","key":"fd21u"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"unstyled","key":"c7qis"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"unstyled","key":"5agso"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"unstyled","key":"4iglt"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"unstyled","key":"7uve5"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"unstyled","key":"b8n7l"},{"data":{},"depth":0,"entityRanges":[],"inlineStyleRanges":[],"text":"","type":"marker","key":"Pv4Xj4JuIlY6azdnpIsj"}],"entityMap":{}},"mentions":[]}