Исполнитель преобразует число на экране. Он умеет выполнять команды: $A$ — прибавить 1, $B$ — прибавить 3, $C$ — умножить на 3. Сколько существует программ, которые при исходном числе 3 получают…
- 1
Обозначим через $f(n)$ количество программ, переводящих число 3 в число $n$. Для последнего шага программы возможны команды $A$, $B$ и $C$, поэтому учитываются переходы из $n-1$, $n-3$ и $n/3$.$$f(n)=f(n-1)+f(n-3)+f(n/3)$$
- 2
Последовательно вычисляя значения от 3 до 14, получаем количество программ, переводящих 3 в 14:$$f(14)=46$$
Ещё 2 қадам — толық шешімде
Исполнитель преобразует число на экране. У него есть две команды: прибавить 1 и умножить на 2. Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при…
- 1
Обозначим через $f(n)$ количество программ перехода из 1 в число $n$. Последняя команда перед получением $n$ либо прибавляет 1, либо умножает число на 2.$$f(n)=f(n-1)+f(n/2)\text{ при чётном }n$$
- 2
Последовательно вычисляя значения, получаем количество способов попасть из 1 в 10:$$f(1)=1,\ f(2)=2,\ f(3)=2,\ f(4)=4,\ f(5)=4,\ f(6)=6,\ f(7)=6,\ f(8)=10,\ f(9)=10,\ f(10)=14$$
Ещё 2 қадам — толық шешімде
303ФИПИ DD7C72№ 23Күрделі Исполнитель преобразует число, записанное на экране. Он выполняет команды: A — прибавить 1, B — прибавить 2, C — умножить на 2. Программа для исполнителя — это последовательность команд. Сколько…
- 1
Обозначим через $f(n)$ количество программ, переводящих число 4 в число $n$. Для последнего шага в число $n$ могли использоваться команды A, B или C, поэтому учитываются переходы из $n-1$, $n-2$ и, если $n$ чётно, из $n/2$.
- 2
Последовательно вычисляем значения от 4 до 11:$$f(4)=1,\ f(5)=1,\ f(6)=2,\ f(7)=3,\ f(8)=6,\ f(9)=9,\ f(10)=16,\ f(11)=25$$
Ещё 3 қадам — толық шешімде
Исполнитель преобразует число на экране. У исполнителя есть три команды: A — вычесть 1; B — вычесть 3; C — найти целую часть от деления на 2. Программа для исполнителя — это последовательность…
- 1
Так как все команды уменьшают число, каждую программу можно рассматривать как путь от 19 к 3. Условие о наличии числа 12 позволяет разделить путь на участок от 19 до 12 и участок от 12 до 3.
- 2
Для каждого числа вычисляем количество способов попасть в него командами A, B и C. Переходы, приводящие в число 9, исключаем; переход C из числа n приводит в число $\lfloor n/2 \rfloor$.
Ещё 2 қадам — толық шешімде
Исполнитель Кантата преобразует число на экране. У исполнителя есть три команды: 1) прибавить 1; 2) прибавить 2; 3) умножить на 3. Программа для исполнителя Кантата — это последовательность команд…
- 1
Поскольку все команды увеличивают число, любая программа, проходящая через 9, сначала достигает 9, а затем движется к 19. Поэтому количество подходящих программ равно произведению числа путей от 2 до 9 и числа путей от 9 до 19, не…$$N = N_{2\to 9} \cdot N_{9\to 19}$$
- 2
Обозначим через $f(n)$ количество способов получить число $n$ из 2. Используем переход по последней команде: прибавление 1, прибавление 2 или умножение на 3.$$f(n)=f(n-1)+f(n-2)+\begin{cases}f(n/3),& n\text{ кратно }3\\0,&\text{иначе}\end{cases}$$
Ещё 3 қадам — толық шешімде
306ФИПИ DE8735№ 23Күрделі Исполнитель преобразует число на экране. У него есть две команды: «Прибавь 2» и «Умножь на 2». Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при…
- 1
Обозначим через $f(n)$ количество программ, переводящих исходное число 1 в число $n$. Последняя команда программы может быть «Прибавь 2» или, если $n$ чётно, «Умножь на 2». Поэтому $f(n)=f(n-2)+f(n/2)$ для чётных $n$ и $f(n)=f(n-2)$ для…$$f(n)=f(n-2)+\begin{cases}f(n/2),& n\text{ чётно},\\0,& n\text{ нечётно}.\end{cases}$$
- 2
Последовательно вычисляя значения от 1 до 18, получаем $f(18)=16$. Это число программ, которые переводят 1 в 18.
Ещё 2 қадам — толық шешімде
307ФИПИ E1D1CF№ 23Күрделі Исполнитель Вычислитель преобразует число, записанное на экране. У исполнителя есть три команды: прибавить 2, умножить на 2 и прибавить 3. Программа для Вычислителя — это последовательность команд…
- 1
Так как траектория должна содержать число 8, каждую программу можно однозначно разделить на участок от 1 до 8 и участок от 8 до 18.$$N = N_{1\to 8}\cdot N_{8\to 18}$$
- 2
Для каждого числа последовательно подсчитываем количество способов получить его с помощью команд «прибавить 2», «умножить на 2» и «прибавить 3», учитывая только допустимые переходы.$$f(n)=f(n-2)+f\left(\frac{n}{2}\right)+f(n-3)$$
Ещё 1 қадам — толық шешімде
308ФИПИ E28170№ 23Күрделі Исполнитель Минус преобразует число на экране. У исполнителя есть две команды: вычесть 2 и вычесть 5. Программа для исполнителя Минус — это последовательность команд. Сколько существует программ…
- 1
Общее уменьшение числа при переходе от 23 к 2 равно 21.$$23 - 2 = 21$$
- 2
Пусть команда «вычесть 2» выполняется $a$ раз, а команда «вычесть 5» — $b$ раз. Тогда количество вариантов команд удовлетворяет уравнению:$$2a + 5b = 21$$
Ещё 4 қадам — толық шешімде
Исполнитель преобразует число на экране. У исполнителя есть две команды: вычесть 1 и найти целую часть от деления на 2. Программа для исполнителя — это последовательность команд. Сколько существует…
- 1
Рассмотрим количество программ, переводящих число $n$ в число 12. Для последнего действия перед достижением результата $n$ возможны переходы из $n-1$ командой A и из $\lfloor n/2\rfloor$ командой B.$$f(n)=f(n-1)+f(\lfloor n/2\rfloor)$$
- 2
При вычислении от 12 до 30 получаем: $f(30)=8$. Это количество программ, которые переводят 30 в 12.
Ещё 2 қадам — толық шешімде
Исполнитель Аллегро преобразует число на экране. Команды исполнителя: прибавить 1, прибавить 2, умножить на 3. Программа представляет собой последовательность команд. Траектория вычислений…
- 1
Обозначим через $f(n)$ число программ, переводящих число 4 в число $n$. Для каждого числа учитываем последние команды: прибавление 1, прибавление 2 и умножение на 3.$$f(n)=f(n-1)+f(n-2)+f(n/3), если n делится на 3$$
- 2
Число программ, переводящих 4 в 10, равно 13.
Ещё 3 қадам — толық шешімде
Исполнитель Вычислитель преобразует число, записанное на экране. Он умеет выполнять команды: прибавить 1, прибавить 2 и умножить на 3. Сколько существует программ, которые преобразуют исходное число…
- 1
Вычислим количество программ, переводящих число 2 в каждое число до 9. Обозначим это количество через $f(n)$. Для числа, кратного 3, учитываем также переход из $n/3$.$$f(n)=f(n-1)+f(n-2)+[3\mid n]f(n/3)$$
- 2
Получаем значения: $f(2)=1$, $f(3)=1$, $f(4)=2$, $f(5)=3$, $f(6)=6$, $f(7)=9$, $f(8)=15$, $f(9)=25$.
Ещё 2 қадам — толық шешімде
312ФИПИ EC38B4№ 23Күрделі Исполнитель преобразует число на экране. У исполнителя есть две команды: 1. Прибавить 1. 2. Умножить на 2. Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для…
- 1
Обозначим через $f(n)$ количество программ, переводящих число 2 в число $n$. Для нечётного $n$ последняя команда может быть только «прибавить 1», а для чётного возможны обе команды.$$f(n)=f(n-1)+f\left(\frac{n}{2}\right)\text{ при чётном }n;\quad f(n)=f(n-1)\text{ при нечётном }n$$
- 2
Последовательно получаем значения до числа 14: $f(2)=1$, $f(3)=1$, $f(4)=2$, $f(6)=3$, $f(8)=5$, $f(10)=7$, $f(12)=10$, $f(14)=13$.
Ещё 2 қадам — толық шешімде
Исполнитель преобразует число на экране. У исполнителя есть две команды: A — прибавь 1; B — поменяй местами. Команда A увеличивает число на экране на 1. Команда B применяется только к числу, у…
- 1
Рассмотрим все допустимые переходы из исходного состояния 100. Команда A увеличивает текущее число на 1, а команда B выполняет перестановку двух последних цифр только при условии, что цифра десятков меньше цифры единиц.
- 2
Последовательно перебираем достижимые числа и для каждого числа сохраняем количество программ, которыми оно получено. При переходе по команде A значение увеличивается на 1; при допустимом переходе по команде B добавляется способ перейти к…
Ещё 1 қадам — толық шешімде
Исполнитель преобразует число на экране. Команда A увеличивает число на экране на 1. Команда B применяется только к числу, у которого цифра в разряде десятков по значению меньше цифры, стоящей в…
- 1
Обозначим через f(n) количество программ, переводящих число 100 в число n. Из 100 можно начать только командой A, поэтому f(100)=1.
- 2
Для любого числа n переход по команде A приходит из числа n-1. Дополнительный переход по команде B возможен, если перестановка двух последних цифр числа-источника разрешена.
Ещё 4 қадам — толық шешімде
315ФИПИ F1FE67№ 23Күрделі Исполнитель К17 преобразует число, записанное на экране. Он выполняет команды: прибавить 1, прибавить 2 или умножить на 2. Сколько существует программ, которые преобразуют исходное число 3 в число…
- 1
Обозначим через $f(n)$ количество программ, переводящих число 3 в число $n$. Для получения $n$ последней командой можно было получить $n-1$, получить $n-2$ или, если $n$ чётно, получить $n/2$.$$f(n)=f(n-1)+f(n-2)+f(n/2)\quad\text{для чётного }n$$
- 2
Последовательно вычисляем количество способов от 3 до 9: $f(3)=1$, $f(4)=1$, $f(5)=2$, $f(6)=4$, $f(7)=6$, $f(8)=11$, $f(9)=17$.$$f(9)=f(8)+f(7)=11+6=17$$
Ещё 3 қадам — толық шешімде
316ФИПИ F27CB9№ 23Күрделі Исполнитель Вычислитель преобразует число, записанное на экране. У него есть три команды: прибавить 1, прибавить 2 и умножить на 2. Программа для Вычислителя — это последовательность команд. Сколько…
- 1
Посчитаем количество программ, переводящих 4 в каждое число до 11. Для числа $n$ последняя команда может быть прибавлением 1, прибавлением 2 или умножением на 2.$$f(n)=f(n-1)+f(n-2)+f(n/2)\text{ при чётном }n$$
- 2
Последовательно получаем: $f(4)=1$, $f(5)=1$, $f(6)=2$, $f(7)=3$, $f(8)=6$, $f(9)=9$, $f(10)=16$, $f(11)=25$.
Ещё 2 қадам — толық шешімде
На обработку поступает натуральное число, не превышающее $10^9$. Программа должна вывести максимальную цифру числа, кратную 3. Если цифр, кратных 3, в числе нет, требуется вывести «NO». Известно…
- 1
При вводе 105 программа последовательно рассматривает цифры 5, 0 и 1. Цифра 0 кратна 3, но переменная maxDigit изначально равна 0, поэтому условие digit > maxDigit для цифры 0 ложно.
- 2
После обработки всех цифр значение maxDigit остаётся равным 0. Проверка maxDigit > 0 также ложна, поэтому программа выводит NO.
Ещё 3 қадам — толық шешімде
На обработку поступает натуральное число, не превышающее $10^9$. Нужно написать программу, которая выводит на экран минимальную цифру числа, кратную 6. Если в числе нет цифр, кратных 6, требуется…
- 1
При вводе числа 125 программа сначала присваивает minDigit значение последней цифры: 5. Затем она проверяет цифры 5, 2 и 1. Ни одна из них не кратна 6, поэтому minDigit не изменяется и программа выводит 5.
- 2
Пример трёхзначного числа, при котором исходная программа выдаёт верный ответ, — 126. В числе есть цифра 6, кратная 6, а цифры 1 и 2 не кратны 6. Программа выводит 6, что является правильным ответом.
Ещё 3 қадам — толық шешімде
319ФИПИ 7E659E№ 24Күрделі Текстовый файл состоит из символов $T$, $U$, $V$, $W$, $X$, $Y$ и $Z$. Определите в прилагаемом файле максимальное количество идущих подряд символов (длину непрерывной подпоследовательности), среди…
- 1
Последовательно просматриваем символы файла, поддерживая текущее окно непрерывной подпоследовательности и количество символов $X$ в нём.$$count_X \leq 140$$
- 2
Если при добавлении очередного символа количество $X$ становится больше 140, сдвигаем левую границу окна, пока условие снова не выполнится.
Ещё 1 қадам — толық шешімде
На обработку поступает натуральное число, не превышающее $10^9$. Нужно написать программу, которая выводит на экран максимальную цифру числа, кратную 5. Если в числе нет цифр, кратных 5, требуется…
- 1
При вводе числа 132 программа сначала выполняет присваивание maxDigit = N % 10, поэтому maxDigit получает значение 2.
- 2
Затем программа последовательно рассматривает цифры 2, 3 и 1. Ни одна из них не делится на 5, поэтому значение maxDigit не изменяется.
Ещё 6 қадам — толық шешімде