Щелчок 2023 | Задание №23 (все прототипы)

Еще не подключил бесплатный Щелчок по всем предметам?

Выбирай курс, переходи по ссылке и присоединяйся ❤️
Прямые ссылки на подключение нужного предмета 👇

ЕГЭ

ОГЭ

Наши каналы:
✔️Математика с МО и русский язык с ТА (Основной канал Школково):

00:00:00 - Старт! Чему мы научимся?
00:00:30 - Задача №1: команды +8 или *2. Из 3 в 86. Разбираем ТЕОРИЮ.
00:05:07 - Разбираем номера (подход к проге).
00:06:15 - Пишем динамическое решение через массивы.
00:09:15 - Второе решение - рекурсией.
00:13:03 - Задача №2: команды +8 или *2 или прибавить предыдущее.
00:14:44 - Пишем динамическое решение.
00:17:00 - Пишем рекурсивное решение.
00:18:22 - Задача №3: команды число единиц +2, прибавить предыдущее, число десятков +1. Динамика.
00:22:32 - Задача №4: команды -3 или раздели на 2 с округлением вниз. Рекурсия и динамика.
00:26:44 - Задача №5: команды -1 или вычти минимальную ненулевую цифру тек. числа. Рекурсия и динамика.
00:36:46 - Задача №6: команды вычти предыдущее или вычти максимальную цифру тек. числа. Рекурсия.
00:39:47 - Задача №7
00:46:15 - Задача №8
00:48:19 - Задача №9
00:50:34 - Задача №10
00:54:53 - Задача №11
00:56:53 - Задача №12
00:58:34 - Задача №13
01:04:02 - Задача №14
01:07:45 - Задача №15
01:11:17 - Задача №16
01:13:10 - Задача №17
01:14:44 - Задача №18
01:17:05 - Задача №19
01:27:45 - Задача №20
01:29:00 - Задача №21

[inf_shkolkovo]

00:00:00 - Старт! Чему мы научимся?
00:00:30 - Задача №1: команды +8 или *2. Из 3 в 86. Разбираем ТЕОРИЮ.
00:05:07 - Разбираем номера (подход к проге).
00:06:15 - Пишем динамическое решение через массивы.
00:09:15 - Второе решение - рекурсией.
00:13:03 - Задача №2: команды +8 или *2 или прибавить предыдущее.
00:14:44 - Пишем динамическое решение.
00:17:00 - Пишем рекурсивное решение.
00:18:22 - Задача №3: команды число единиц +2, прибавить предыдущее, число десятков +1. Динамика.
00:22:32 - Задача №4: команды -3 или раздели на 2 с округлением вниз. Рекурсия и динамика.
00:26:44 - Задача №5: команды -1 или вычти минимальную ненулевую цифру тек. числа. Рекурсия и динамика.
00:36:46 - Задача №6: команды вычти предыдущее или вычти максимальную цифру тек. числа. Рекурсия.
00:39:47 - Задача №7: команды +1 или *4 или +3. Траектория СОДЕРЖИТ число. Разбираем рекурсию и динамику.
00:46:15 - Задача №8: команды прибавь сумму цифр числа или *2 или +1. Рекурсия.
00:48:19 - Задача №9: команды -3 или зачеркни последнюю цифру числа. Содержит число. Динамика.
00:50:34 - Задача №10: команды -2 или вычесть минимальную ненулевую цифру числа. НЕ СОДЕРЖИТ число. Рекурсия и динамика.
00:54:53 - Задача №11: команды -1 или вычесть сумму цифр числа. Не содержит число. Рекурсия.
00:56:53 - Задача №12: команды прибавь сумму цифр числа или прибавь предыдущее. Не содержит 2 числа. Рекурсия.
00:58:34 - Задача №13: команды -1 или //2 или вычесть последнюю цифру числа. Содержит 13 КОМАНД. Рекурсия.
01:04:02 - Задача №14: команды -1 или -2 или вычесть минимальную ненулевую цифру числа. Содержит 16 КОМАНД. Рекурсия.
01:07:45 - Задача №15: команды +половина числа или +2 или +предыдущее. Содержит 23 КОМАНДЫ. Рекурсия.
01:11:17 - Задача №16: команды +1 или *2 или прибавь минимальную цифру. Содержит и не содержит числа. Рекурсия.
01:13:10 - Задача №17: команды +1 или +2 или ^2. Не содержит число и содержит 20 КОМАНД. Рекурсия.
01:14:44 - Задача №18: команды -3 или //2 или вычесть последнюю цифру. Не содержит 2 числа и содержит 15 КОМАНД. Рекурсия.
01:17:05 - Задача №19: команды +2 или *2+1. Сколько различных РЕЗУЛЬТАТОВ? Ровно 12 КОМАНД. Рекурсия.
01:27:45 - Задача №20: команды *2 или *2+1. Сколько различных РЕЗУЛЬТАТОВ? Ровно 5 КОМАНД. Генерация команд перебором.
01:29:00 - Задача №21: команды +1 или +3 или *3. Сколько РЕЗУЛЬТАТОВ? Содержит 10 КОМАНД. Траектория содержит не более 3 нечетных числа.

[pomidorka_]

спасибо за разбор жёстких 23, АР как всегда на высшем уровне

[kalashsalieri]

мимимамаму мимимамаму слова пацана с азии я тоже солидарен с ним

[natari]

В 19 задаче очень быстро работает такой код:
a = [6]
l=0
While l < 12:
for i in range(len(a)):
a.append(a[0]+2)
a.append(a[0]*2+1)
a.pop(0)
l+=1
print(len(set(a)))

[gowent]

так в итоге, чей ответ верен? вы уверены, что не ошиблись в решении, где ответ не совпал с ответами? просто он не совпал 2 раза подряд в тот момент, когда появилось новое условие на Кол-во команд

[iskap]

на 54:40 не учтена 9 в цикле for x in range(1, 9)

[ydmusic]

У меня одного код для 9 задачи не работает? Вылазит ошибка: list index out of range

[minecraftbuilding]

from itertools import product

def f(start, com):
if com == 1:
return start + 1
elif com == 2:
return com + 3
else:
return start * 3
ans = set()
number = range(1, 4)
res = tuple(product(number, repeat=10))
for i in res:
flag = True
start = 2
nechet = 0
for x in i:
start = f(start, x)
if start % 2 == 1:
nechet += 1
if nechet > 3:
flag = False
if flag == True:
ans.add(start)
print(len(ans))

объясните пожалуйста почему такая вариация 21 номера не работает, где тут ошибка?
выводит ответ 307

[ixlwunc]

АР, так мин ненулевое число это 1, просто бы добавил один?

[gowent]

обьясните, почему в 1:04:00 у нас в принте к=0 а не 13??

[LordBulbator]

я один в рекурсиях затупил на переполненности стэка функции?

[tulmxgu]

Здравствуйте, уважаемый АР, я хочу немного понаглеть и сказать, что ваша программа для динамики на 36:16 излишне сложна)
Вы каждый раз для числа i ищете те числа, из которых можно прийти в это самое число i, но, как минимум в этой задаче, проще делать наоборот: для каждого i искать числа, в которые мы можем отсюда прийти

Получится примерно такая программа:

dp = [0] * 34
dp[33] = 1

for i in range(33, 12, -1):
dp[i - 1] += dp[i]
dp[i - min([int(j) for j in str(i) if j != '0'])] += dp[i]

print(dp[12])

Такой способ облегчает не только это решение динамикой, поэтому всем сдающим ребятам советую просто помнить, что так тоже можно извернутся, и, возможно, это в каком-то случае спасёт ваш №23. Всем добра и капибары)

[nikita_dushnila]

это действительно уровень егэ? ...




задача 19, АР зачем вы так издеваетесь?)):
d = set()

def f(c, k):
if k==12: d.add(c)
else:
f(c+2, k+1)
f(c*2+1, k+1)
f(6, 0)
print(len(d))

задача 21:

from functools import *

d = set()

@lru_cache(None)
def f(c, k, p):
if c%2!=0: p+=1
if k==10: #главное условия через два if, а не через and
if p<=3:
d.add(c)
else:
f(c+1, k+1, p+0)
f(c+3, k+1, p+0)
f(c*3, k+1, p+0)

f(2, 0, 0)
print(len(d))

[jonymaks]

Вы меня извините, но исполнитель «Шабат» оскорбляет чувства верующих, просьба изменит это..

[FacelessFiore]

15 задача:
from functools import lru_cache

@lru_cache(None) #(подключать lru_cache не обязательно, рекурсия не уходит слишком глубоко, я просто привык подключать всегда)
def f(st, fin, k):
if k > 23:
return 0
if st == fin and k == 23:
return 1
if st > fin:
return 0
if st == fin and k != 23:
return 0

x = f(st + 2, fin, k + 1)
y = f(st + (st-1), fin, k + 1)
if st % 2 == 0:
z = f(st + (st/2), fin, k + 1)
else:
z = 0
return x+y+z

print(f(2, 39, 0))
Ответ: 0

[wvmthdd]

Номер 14:
from functools import *
@lru_cache(None)
def f(x, y, k):
if x < y: return 0
if k > 16: return 0
if x == y: return k == 16

return f(x-1, y, k+1) + f(x-2, y, k+1) + f(x - (min(int(t) for t in str(x) if t != 0)), y, k+1)
print(f(32, 8, 0))
ответ 4681154