Задание 19-21 // КЕГЭ по информатике 2024

Обновляем алгоритм решения ТИГРа и разбираем решение 19-21 программно

За мат, КАПС, политоту, флуд - перманентный бан.

--------------------------------------------------------------------------------------------

Ссылки на каналы других годных преподавателей:

Таймкоды
00:00 Приветствие
03:35 Про обновление функции
11:00 Как работает функция наглядно
32:00 Одна куча камней
43:00 Одна куча камней (с проигрышем)
49:10 Две кучи камней
57:15 Две кучи камней (с уменьшением)
01:03:02 Две кучи камней
01:10:45 Проверка ходов II
01:29:00 Проверка ходов II
01:41:20 Перебор двух куч
01:51:50 Три кучи камней
01:56:15 Окончание и напутствия

[AbcDef-lsri]

Пересмотрел множество стримов по теории игр, и только ваш помог мне понять её. Спасибо большое

[frodobaggins]

Это просто нечто, спасибо! Спасибо за всё, что вы делаете, ваши вебы и наикрутейший сайт невероятно помогли мне и огромному количеству 11-классников по всей России, я просто невероятно благодарна вам за такое количество полезного материала в открытом доступе, разобранного максимально понятно. Успехов вам и всего наилучшего!

[peeneska]

ааааааа это такая имба!!! код максимально короток, но при этом так много смысла. стоит лишь 1 раз понять его принцип, и это в разы ускоряет решение, нежели решать другим кодом. Алексей, спасибо!

[keuky]

в школе учили экселем, репетитор учил ручками) если одну кучу руками еще можно, то с двумя как карта ляжет: не всегда в нужное русло силы направишь, потратишь еще больше времени) а с питоном все проще и, как мне кажется, понятнее) про эксель вообще молчу: там пока таблицы построишь, уже минут 5 потратишь

[monieKidd]

наконец-то допер. два дня осиливал идею, спасибо Алексей!

[RudyFoxAngel]

Алексей, вечер добрый! Не знаю актуально или нет, но можно под косячит Петя или нет ввести параметр, который по умолчанию принимает значение 0 (не косясит) def fn(s, m, n=0): тогда последняя строчка примет вид return any(h) if (m - 1) % 2 == 0 else all(h) if n == 0 else any(h)

[алексейсуворов-нз]

Огромное Вам спасибо смотрим Ваши стримы на уроках

[anachorett]

Спасибо, очень классный метод решения

[мастеркрая-эъ]

Очень понятное объяснение, спасибо за решение!😺

[krosh]

просто нужно понимать - мы не отвечаем за ход соперника, поэтому должны учесть оба его хода ( 2 true ), но когда наступает наш ход - достаточно и 1 (1-2 true) правильного возможного ответвления (хода) ?

[dwaynebarry]

спс за красивое объяснение работы рекурсии

[asddsasi]

1:10:57 - можно переделать возвращаемое значение функции проигравшего в нашу программу без смены all на any! Тем самым выполнить 3 условие 21 задания и эта переделка не повлияет на ответы предыдущих заданий.
#Проверка ходов (1) (две кучи камней)
def Win(c, d, l):
return 0 if c==d else any([Lose(min(c, d)+1, max(c, d), l-1)[0], Lose(min(c, d)+3, max(c, d), l-1)[0]])
def Lose(a, b, k):
return [1] if a==b else [0] if not k else [all([Win(min(a, b)+1, max(a, b), k-1), Win(min(a, b)+3, max(a, b), k-1)]),
[Win(min(a, b)+1, max(a, b), k-1), Win(min(a, b)+3, max(a, b), k-1)]]
print(min([i for i in range(1, 24) if i!=13 and Lose(13, i, 2)[0]]))#9
print(*[i for i in range(1, 24) if not Win(13, i, 1) and Win(13, i, 3)][:2])#6, 8
print(*[i for i in range(1, 24) if i!=13 and all((not Lose(13, i, 2)[0], Lose(13, i, 4)[0], True in Lose(13, i, 2)[1]))])#7, 19

1:29:00 - всё тоже самое только для одной кучи камней!
#Проверка ходов (2) (одна куча камней)
def Win(m, l):
return [0] if m>=41 else [any([Lose(m+1, l-1), Lose(m+2, l-1)]), [Lose(m+1, l-1), Lose(m+2, l-1)]] if 50-m*2<0\
else [any([Lose(m+1, l-1), Lose(m+2, l-1), Lose(m*2, l-1)]), [Lose(m+1, l-1), Lose(m+2, l-1), Lose(m*2, l-1)]]
def Lose(n, k):
return 1 if n>=41 else 0 if not k else all([Win(n+1, k-1)[0], Win(n+2, k-1)[0]]) if 50-n*2<0\
else all([Win(n+1, k-1)[0], Win(n+2, k-1)[0], Win(n*2, k-1)[0]])
print(*[i for i in range(1, 41) if not Lose(i, 2) and Lose(i, 4)])#35
t = [i for i in range(1, 41) if not Lose(i, 2) and not Lose(i, 4) and Lose(i, 6)]; print(min(t), max(t))#17, 32
print(*[i for i in range(1, 41) if all((not Win(i, 1)[0], Win(i, 3)[0], Win(i, 3)[1].count(True)==2))])#19

1:41:21 - прикольная задача
#Перебор двух куч
def Win(c, d, l):
return 0 if c+d>=45 else any([Lose(c+2, d, l-1), Lose(c, d+2, l-1), Lose(c*3, d, l-1), Lose(c, d*3, l-1)])
def Lose(a, b, k):
return 1 if a+b>=45 else 0 if not k else all([Win(a+2, b, k-1), Win(a, b+2, k-1), Win(a*3, b, k-1), Win(a, b*3, k-1)])
print(len([(x, y) for x in range(1, 44) for y in range(1, 44) if x+y<=43 and Lose(x, y, 2)]))#16
t = [i for i in range(1, 44) if not Win(4, i, 1) and Win(4, i, 3)]; print(min(t), max(t))#7, 11
print(*[i for i in range(1, 44) if not Lose(13, i, 2) and Lose(13, i, 4)])#1

1:51:50 - 3 кучи, не беда!
#Три кучи камней
def Win(e, f, g, l):
return 0 if e+f+g>=71 else any([Lose(e+3, f, g, l-1)[0], Lose(e, f+3, g, l-1)[0], Lose(e, f, g+3, l-1)[0],
Lose(e*2, f, g, l-1)[0], Lose(e, f*2, g, l-1)[0], Lose(e, f, g*2, l-1)[0]])
def Lose(a, b, c, k):
return [1] if a+b+c>=71 else [0] if not k else [all([Win(a+3, b, c, k-1), Win(a, b+3, c, k-1), Win(a, b, c+3, k-1),
Win(a*2, b, c, k-1), Win(a, b*2, c, k-1), Win(a, b, c*2, k-1)]),
[Win(a+3, b, c, k-1), Win(a, b+3, c, k-1), Win(a, b, c+3, k-1),
Win(a*2, b, c, k-1), Win(a, b*2, c, k-1), Win(a, b, c*2, k-1)]]
print(min([i for i in range(1, 59) if any(Lose(7, 5, i, 2)[1])]))#15
t = [i for i in range(1, 59) if not Win(7, 5, i, 1) and Win(7, 5, i, 3)]; print(min(t), max(t))#14, 27
print(*[i for i in range(1, 59) if not Lose(7, 5, i, 2)[0] and Lose(7, 5, i, 4)[0]])#24

[RevernBlitz]

Как я понял суть any и all в том, что any применяется условно на нашем ходу и это означает, что если мы подумаем, то найдём хотя бы один путь к победе и конечно же выберем его, а all для противника означает, что он в безвыходной ситуации и ВСЕ его ходы приведут к поражению(нашей победе) и всё это работает на m==0 или на m%2==0 в зависимости от того, результат какого игрока нам нужен

Подскажите, верно ли я всё понял 🙃

[immortalwoods]

Спасибо всем причастным за этот великолепный код

[arkangel]

Алексей, 1:45:38 не могли брать range(1, 44), потому что если в одной из куч будет 43 камня, не выполнится условие для другой кучи k>=1 и s>=1, потому что тогда там должно будет быть 0 камней. хотя с диапазоном (1, 43) Ответ тот же

[АнтонК-шо]

Алексей, добрый день. Будет ли корректно работать условие if (m - 1) % 2 == 0 если заменить его на if m % 2 != 0?

[ИванЦуненков]

Здравствуйте! Стоит ли ожидать задачу с двумя кучами на основной волне и в резерве 23 года? Заметил тенденцию, что остались только задачки с одной кучей, причем и в официальных вариантах, и в авторских вариантах на кегэ.

[mirfy]

Почему на 39:10 мы вписываем, что у Вани нет победы первым ходом, если у него нет лишь стратегии гарантированной победы? То есть в отличии от 2 вопроса, где нам чётко обозначено, что "Петя не может выиграть за один ход", в 3 вопросе сказано, что Ваня МОЖЕТ победить и за один ход тоже, просто не обязательно. Запутался на этом моменте. Условия разные у 2 и 3 вопросов, а запись по итогу одна и та же.

[whitehat-it-]

на решу егэ половина задач, решенная таким методом - неверно

[Прогрессор]

код огонь + 3 балла на егэ ( если тупенький запомни как стишок)