241ФИПИ E8B874№ 22Күрделі Получив на вход натуральное десятичное число $x$, алгоритм печатает два числа: $L$ и $M$. Укажите наибольшее число $x$, при вводе которого алгоритм выводит сначала 16, а потом 3.
- 1
Переменная $M$ увеличивается на единицу при каждом делении $x$ на 6. Поэтому $M=3$ означает, что исходное число имеет ровно три цифры в шестиричной системе счисления.
- 2
Остатки от деления на 6 являются цифрами шестиричной записи числа. Если очередной остаток чётный, он умножается на $L$. Нулевая цифра дала бы $L=0$, поэтому для получения $L=16$ используются цифры 2 или 4.
Ещё 3 қадам — толық шешімде
242ФИПИ EC97B7№ 22Күрделі Ниже на пяти языках программирования записан алгоритм. Получив на вход число $x$, этот алгоритм печатает два числа: $L$ и $M$. Укажите наименьшее число $x$, при вводе которого алгоритм печатает…
- 1
На каждой итерации значение $x$ целочисленно делится на 2, поэтому цикл выполняется столько раз, сколько разрядов в двоичной записи исходного числа. Следовательно, $M=9$ означает, что число должно иметь 9 двоичных разрядов.$$M=9$$
- 2
Увеличение $L$ происходит тогда и только тогда, когда очередной остаток от деления на 2 равен 1. Поэтому $L$ — количество единиц в двоичной записи числа.$$L=5$$
Ещё 2 қадам — толық шешімде
243ФИПИ F168C7№ 22Күрделі Получив на вход число $x$, алгоритм печатает два числа: $S$ и $P$. Укажите наибольшее число $x$, при вводе которого алгоритм печатает сначала $9$, а потом $3$.
- 1
При последовательном делении $x$ на $4$ алгоритм получает цифры числа $x$ в четверичной системе. Пусть $N$ — количество цифр, $A$ — их сумма, а $B$ — произведение.$$S=A+N,\quad P=B+N$$
- 2
По условию $S=9$ и $P=3$, поэтому $A+N=9$ и $B+N=3$. Так как $B\geq0$, имеем $N\leq3$.
Ещё 2 қадам — толық шешімде
244ФИПИ FE3877№ 22Күрделі На вход алгоритма подаётся натуральное число $N$. Алгоритм строит по нему новое число следующим образом: строится двоичная запись числа $N$, затем к этой записи справа дописываются ещё два разряда…
- 1
Если $N$ чётное, к двоичной жазбалар дописываются два нуля, поэтому результат равен $4N$.$$R = 4N$$
- 2
Если $N$ нечётное, к двоичной записи дописываются две единицы. Это означает умножение на $4$ и добавление числа $3$.$$R = 4N + 3$$
Ещё 2 қадам — толық шешімде
245ФИПИ FF7D90№ 22Күрделі Ниже на пяти языках программирования записан алгоритм. Получив на вход число $x$, этот алгоритм печатает два числа: $L$ и $M$. Укажите наименьшее число $x$, при вводе которого алгоритм печатает…
- 1
На каждой итерации число $x$ заменяется на результат целочисленного деления на 2. Поэтому $M$ равно длине двоичной записи исходного числа $x$.
- 2
При проверке остатка от деления на 2 переменная $L$ увеличивается для каждого нечётного остатка, то есть $L$ равно количеству единиц в двоичной записи числа.
Ещё 3 қадам — толық шешімде
246ФИПИ 007C14№ 23Күрделі Исполнитель Минус преобразует число на экране. У исполнителя есть две команды: вычесть 2 и вычесть 5. Первая команда уменьшает число на экране на 2, вторая уменьшает это число на 5. Программа для…
- 1
От числа 17 до числа 1 нужно уменьшить значение на 16.$$17 - 1 = 16$$
- 2
Пусть команда «вычесть 2» выполнена $a$ раз, а команда «вычесть 5» — $b$ раз. Тогда$$2a + 5b = 16$$
Ещё 3 қадам — толық шешімде
Исполнитель преобразует число на экране. Команда 1 уменьшает число на 1, команда 2 заменяет число на целую часть от деления числа на 2. Сколько существует программ, для которых при исходном числе 30…
- 1
Так как обе команды уменьшают число, любая программа, траектория которой содержит 9, однозначно разбивается на путь от 30 до 9 и путь от 9 до 1.
- 2
Обозначим через $f(n)$ число программ перехода из $n$ в 9. Для $n>9$ выполняется рекуррентное соотношение $f(n)=f(n-1)+f(\lfloor n/2\rfloor)$, а $f(9)=1$. Последовательное вычисление даёт $f(30)=14$.$$f(30)=14$$
Ещё 2 қадам — толық шешімде
248ФИПИ 0288EE№ 23Күрделі Исполнитель преобразует число, записанное на экране. У него есть три команды: 1) прибавить 1; 2) прибавить 2; 3) умножить на 3. Сколько существует программ, которые преобразуют исходное число 2 в…
- 1
Поскольку все команды увеличивают число, числа 9 и 11 в траектории могут встретиться только в порядке $9$, затем $11$.
- 2
Посчитаем количество программ из 2 в каждое число до 9. Для числа $n$ учитываем переходы из $n-1$, из $n-2$ и, если $n$ кратно 3, из $n/3$.$$f(2)=1,\ f(3)=1,\ f(4)=2,\ f(5)=3,\ f(6)=6,\ f(7)=9,\ f(8)=15,\ f(9)=15+9+1=25$$
Ещё 3 қадам — толық шешімде
Исполнитель преобразует число на экране. У исполнителя есть три команды: A — вычесть 1; B — вычесть 4; C — найти целую часть от деления на 3. Программа для исполнителя — это последовательность…
- 1
Из каждого текущего числа рассматриваем три возможных перехода: вычитание 1, вычитание 4 и деление на 3 с взятием целой части. Переходы, после которых получается 9, не учитываем.$$A(n)=n-1,\quad B(n)=n-4,\quad C(n)=\left\lfloor\frac{n}{3}\right\rfloor$$
- 2
Для каждого числа храним два значения: количество способов попасть в него без числа 9 и количество способов попасть в него с уже встречавшимся числом 15. При переходе в 15 способ переносится во вторую группу.
Ещё 1 қадам — толық шешімде
Исполнитель преобразует число на экране. У исполнителя есть три команды: A — вычесть 1; B — вычесть 2; C — найти целую часть от деления на 3. Программа для исполнителя — это последовательность…
- 1
Пусть $f(n)$ — число программ, переводящих число $n$ в число 3 и не содержащих в траектории чисел 13 и 14. Для числа 3 учитываем пустую последовательность команд: $f(3)=1$.$$f(3)=1$$
- 2
Последняя команда программы может быть A, B или C. Поэтому для остальных разрешённых значений $n$ количество программ равно сумме количества программ для чисел $n-1$, $n-2$ и $\lfloor n/3\rfloor$.$$f(n)=f(n-1)+f(n-2)+f(\lfloor n/3\rfloor)$$
Ещё 2 қадам — толық шешімде
Исполнитель Вычислитель преобразует число на экране. У исполнителя есть две команды: прибавить 1 и умножить на 2. Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа…
- 1
Обозначим через $f(n)$ количество программ, переводящих число 1 в число $n$. Последняя команда перед получением $n$ могла быть прибавлением 1 или умножением на 2.$$f(n)=f(n-1)+f(n/2)\text{ при чётном }n;\quad f(n)=f(n-1)\text{ при нечётном }n$$
- 2
Последовательно получаем значения до числа 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$$
Ещё 3 қадам — толық шешімде
Исполнитель преобразует число на экране. У исполнителя есть три команды: A — прибавить 2, B — прибавить 3, C — умножить на 2. Программа для исполнителя — это последовательность команд. Сколько…
- 1
Так как все команды увеличивают число, в каждой подходящей программе число 15 встречается один раз. Поэтому программу можно разделить на путь от 3 до 15 и путь от 15 до 25.$$N = N_{3\to15}\cdot N_{15\to25}$$
- 2
Для первой части применяем динамический подсчёт числа программ, исключая состояние 9. Получаем число допустимых путей от 3 до 15.
Ещё 2 қадам — толық шешімде
253ФИПИ 0CCF9C№ 23Күрделі Исполнитель Кантата преобразует число на экране. У исполнителя есть три команды: 1) прибавить 1; 2) умножить на 2; 3) умножить на 3. Программа для исполнителя Кантата — это последовательность…
- 1
Из числа 5 в число 9 можно попасть только последовательным прибавлением единицы: $5 \to 6 \to 7 \to 8 \to 9$. Поэтому начальный участок программы единственный.$$N(5 \to 9)=1$$
- 2
Обозначим через $f(x)$ число способов попасть из 9 в $x$, не проходя через 27. Для остальных чисел используем динамическое программирование: последний шаг мог быть прибавлением 1, умножением на 2 или умножением на 3.$$f(x)=f(x-1)+[2\mid x]f\left(\frac{x}{2}\right)+[3\mid x]f\left(\frac{x}{3}\right)$$
Ещё 2 қадам — толық шешімде
Исполнитель преобразует число на экране. У исполнителя есть две команды: A — прибавь 1; B — поменяй местами. Команда A увеличивает число на экране на 1. Команда B применяется только к числу, у…
- 1
Каждому числу сопоставим количество программ, которые переводят исходное число 111 в это число. Для числа 111 начальное количество программ равно 1.
- 2
Из каждого состояния добавляем переход по команде A: число увеличивается на 1. Также добавляем переход по команде B, если цифра в разряде десятков меньше цифры в разряде единиц; при этом две последние цифры меняются местами.
Ещё 2 қадам — толық шешімде
Исполнитель Вычислитель преобразует число, записанное на экране. Он выполняет команды: умножить число на 3, прибавить 2 или прибавить 3. Программа для Вычислителя — это последовательность команд…
- 1
Обозначим через $f(n)$ количество программ, преобразующих число 2 в число $n$. Для получения $n$ последняя команда могла быть прибавлением 2, прибавлением 3 или умножением на 3.$$f(n)=f(n-2)+f(n-3)+f(n/3), если n делится на 3$$
- 2
Последовательно вычисляя значения, получаем количество программ из 2 в 15:$$f(15)=f(13)+f(12)+f(5)=12+10+1=23$$
Ещё 2 қадам — толық шешімде
Исполнитель преобразует число на экране. Он умеет выполнять команды: прибавить 1, умножить на 2 и умножить на 3. Программа для исполнителя — это последовательность команд. Сколько существует…
- 1
Пусть $f(n)$ — количество программ, переводящих число 2 в число $n$ без появления числа 14 в траектории. Начальное значение: $f(2)=1$, а для запрещённого числа полагаем $f(14)=0$.
- 2
Чтобы получить число $n$, последней могла быть команда прибавления 1, умножения на 2 или умножения на 3. Поэтому учитываются значения $f(n-1)$, $f(n/2)$ и $f(n/3)$ только при целочисленном делении.
Ещё 2 қадам — толық шешімде
257ФИПИ 1D7139№ 23Күрделі Исполнитель К17 преобразует число, записанное на экране. Он выполняет команды: прибавить 1, прибавить 2 или умножить на 2. Программа — это последовательность команд. Сколько существует программ…
- 1
Сначала подсчитаем количество программ, переводящих число 4 в число 10. Обозначим через f(n) число способов получить n из 4.$$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(10)=f(9)+f(8)+f(5)=9+6+1=16$$
Ещё 3 қадам — толық шешімде
258ФИПИ 1FC322№ 23Күрделі Исполнитель «Вычислитель» преобразует число, записанное на экране. У исполнителя есть три команды: 1) прибавить 1; 2) умножить на 2; 3) прибавить 3. Программа для «Вычислителя» — это…
- 1
Для подсчёта числа программ, ведущих из 3 в заданное число, используем динамику: последний шаг может быть прибавлением 1, умножением на 2 или прибавлением 3.$$f(n)=f(n-1)+f(n/2)+f(n-3)$$
- 2
Вычисляя значения от 3 до 10, получаем: $f(3)=1$, $f(4)=1$, $f(5)=1$, $f(6)=3$, $f(7)=4$, $f(8)=6$, $f(9)=9$, $f(10)=14$.
Ещё 3 қадам — толық шешімде
259ФИПИ 209B53№ 23Күрделі Исполнитель преобразует число на экране. У исполнителя есть три команды: $A$ — прибавить 1, $B$ — прибавить 3, $C$ — умножить на 3. Программа для исполнителя — это последовательность команд. Сколько…
- 1
Обозначим через $f(n)$ количество программ, переводящих число 3 в число $n$ без прохождения через 9 и 15. Для разрешённого числа способы попасть в него приходят из $n-1$ командой $A$, из $n-3$ командой $B$, а также из $n/3$ командой $C$…$$f(n)=f(n-1)+f(n-3)+f(n/3)$$
- 2
Для запрещённых чисел устанавливаем $f(9)=0$ и $f(15)=0$. Начальное значение: $f(3)=1$.
Ещё 2 қадам — толық шешімде
Исполнитель преобразует число на экране. У него есть две команды: A — вычти 1; B — найди целую часть от деления на 2. Программа для исполнителя — последовательность команд. Сколько существует…
- 1
Обозначим через $f(n)$ число программ, переводящих число $n$ в заданное конечное число. Последняя команда может быть A, тогда перед ней было $n-1$, или B, тогда перед ней было $\lfloor n/2\rfloor$.$$f(n)=f(n-1)+f(\lfloor n/2\rfloor)$$
- 2
Для перехода из 30 в 8 вычисление рекуррентно даёт: $f(8)=1$, затем $f(9),\ldots,f(15)=1$, $f(16)=2$, и далее $f(30)=16$.
Ещё 2 қадам — толық шешімде