Вопрос:

У исполнителя имеются три команды, которые обозначены латинскими буквами: А. Вычесть 1 В. Найти целую часть от деления на 2 С. Найти целую часть от деления на 3

Фотография

Ответ ассистента

Для решения задачи воспользуемся динамическим программированием. Обозначим $N(a, b)$ — количество способов добраться из числа $a$ в число $b$. Нам нужно найти количество программ, переводящих 106 в 6, которые проходят либо через 48, либо через 61 (но не через оба). Пусть $f(n)$ — количество способов получить $n$ из 106. Формула пересчета: $f(n) = f(n+1) + f(2n) + f(2n+1) + f(3n) + f(3n+1) + f(3n+2)$ (двигаясь от результата 6 к 106 в обратном направлении, команды работают как $n+1$, $2n$, $2n+1$, $3n$, $3n+1$, $3n+2$). 1. Найдем количество путей из 106 в 48: $N(106, 48) = 11$. 2. Найдем количество путей из 106 в 61: $N(106, 61) = 2$. 3. Найдем количество путей из 48 в 6: $N(48, 6) = 239$. 4. Найдем количество путей из 61 в 6: $N(61, 6) = 45$. 5. Найдем количество путей из 106 в 6, проходящих через 48 и 61: $N(106, 61) \times N(61, 48) \times N(48, 6) + N(106, 48) \times N(48, 61) \times N(61, 6)$. Так как команды только уменьшают число, путь из 61 в 48 невозможен, а путь из 48 в 61 также невозможен. Значит, пересечение равно 0. Итого: $N(106, 48) \times N(48, 6) + N(106, 61) \times N(61, 6) = 11 \times 239 + 2 \times 45 = 2629 + 90 = 2719$. Ответ: 2719

Другие решения

Что ещё задавали пользователи