Решайте задания по одному, проверяйте себя сразу и открывайте подсказки там, где нужно.
1. Прибавь 1
2. Прибавь 2
3. Прибавь 5Первая команда увеличивает число на экране на 1, вторая — на 2, третья — на 5. Программа для исполнителя А25S — это последовательность команд.
Верный ответ: 15571
Все три команды увеличивают число на фиксированную величину: 1, 2 или 5. Обозначим F(n) — число программ, переводящих 2 в n.
Последняя команда могла быть:
• «+1», тогда перед n находилось n − 1;
• «+2», тогда перед n находилось n − 2;
• «+5», тогда перед n находилось n − 5.
Поэтому F(n)=F(n−1)+F(n−2)+F(n−5). Значения для чисел меньше 2 считаем нулевыми, а F(2)=1 — пустая программа.
Последовательно получаем:
F(3)=1, F(4)=2, F(5)=3, F(6)=5, F(7)=9, F(8)=15, F(9)=26, F(10)=44, F(11)=75, F(12)=128, F(13)=218, F(14)=372, F(15)=634, F(16)=1081, F(17)=1843, F(18)=3142, F(19)=5357, F(20)=9133.
Для 21: F(21)=F(20)+F(19)+F(16)=9133+5357+1081=15571.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19216.
Верный ответ: 31
Нужно учесть два непересекающихся случая: траектория содержит 11, но не 12, либо содержит 12, но не 11. Число 20 запрещено в обоих случаях.
Для команд «+1» и «×2» используем динамику: F(n)=F(n−1), если n нечётно, и F(n)=F(n−1)+F(n/2), если n чётно. Запрещённым значениям присваиваем 0.
Случай 1: есть 11, нет 12.
Из 2 в 11 существует 7 программ. После 11 нельзя выполнить «+1», потому что получится 12, поэтому приходится перейти 11→22 командой «×2». Затем до 40 можно только прибавлять 1; число 20 уже осталось позади. Продолжение единственно. Получаем 7 · 1 = 7 программ.
Случай 2: есть 12, нет 11.
Из 2 в 12 без числа 11 существует 3 программы. Из 12 в 40 без числа 20 существует 8 программ: при последовательном расчёте F(20)=0, затем F(24)=1, F(28)=2, F(32)=4, F(36)=6, F(40)=8. Получаем 3 · 8 = 24 программы.
Складываем два несовместимых случая: 7 + 24 = 31.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19189.
Верный ответ: 13
Разложим числа на простые множители: 8 = 23, 2048 = 211. В конечном числе нет множителя 3. Если хотя бы один раз выполнить команду «Умножить на 3», множитель 3 появится и уже не исчезнет, поскольку все команды только умножают. Поэтому вторую команду использовать нельзя.
Нужно увеличить показатель степени двойки с 3 до 11, то есть набрать ещё 8 единиц показателя.
Команда «×2» увеличивает показатель на 1, а команда «×8» = «×23» увеличивает его на 3. Значит, задача сводится к подсчёту последовательностей шагов 1 и 3 с суммой 8.
Обозначим F(k) количество таких последовательностей с суммой k. Последний шаг равен либо 1, либо 3, поэтому F(k)=F(k−1)+F(k−3), F(0)=1, а для отрицательных индексов значение равно 0.
Получаем F(1)=1, F(2)=1, F(3)=2, F(4)=3, F(5)=4, F(6)=6, F(7)=9, F(8)=13.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19162.
Верный ответ: 13
Фраза «ровно одно из чисел 9 и 10» задаёт два непересекающихся случая:
1) траектория проходит через 9 и не проходит через 10;
2) траектория проходит через 10 и не проходит через 9.
Для команд «+1» и «×2» число способов получить n считается по формуле F(n)=F(n−1)+F(n/2) для чётного n и F(n)=F(n−1) для нечётного. Запрещённому числу присваивается 0.
Случай через 9.
Из 2 в 9 существует 5 программ. После 9 нельзя попадать в 10: команда «+1» запрещена, поэтому единственный допустимый первый шаг — 9→18. Далее до 24 остаётся только прибавлять 1. Получается 5 · 1 = 5 программ.
Случай через 10.
Из 2 в 10 без прохождения через 9 существует 2 программы. Из 10 в 24 существует 4 программы. Получается 2 · 4 = 8 программ.
Случаи несовместимы, поэтому количества складываются: 5 + 8 = 13.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19135.
- прибавь 1
- прибавь 2
- прибавь предыдущееПервая команда увеличивает число на экране на 1, вторая увеличивает это число на 2, третья прибавляет к числу на экране число, меньшее на 1 (к числу 3 прибавляется 2, к числу 11 прибавляется 10 и т. д.). Программа для исполнителя – это последовательность команд. Сколько существует программ, которые число 2 преобразуют в число 9?
Верный ответ: 57
Третья команда для числа x даёт x + (x − 1) = 2x − 1. Будем считать F(n) — число программ, переводящих 2 в n.
К числу n можно прийти:
• из n − 1 командой «+1»;
• из n − 2 командой «+2»;
• если n нечётно, из (n + 1) / 2 командой «Прибавь предыдущее», потому что 2 · ((n + 1) / 2) − 1 = n.
Разные команды считаются разными программами, даже когда они приводят к одинаковому результату. Например, из 2 в 3 ведут и команда «+1», и третья команда, поэтому F(3)=2.
Последовательно получаем:
F(2)=1;
F(3)=1+1=2;
F(4)=F(3)+F(2)=3;
F(5)=F(4)+F(3)+F(3)=7;
F(6)=F(5)+F(4)=10;
F(7)=F(6)+F(5)+F(4)=20;
F(8)=F(7)+F(6)=30;
F(9)=F(8)+F(7)+F(5)=30+20+7=57.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19108.
1. Прибавить 1
2. Умножить на 2
3. Прибавить 3Первая команда увеличивает число на экране на 1, вторая умножает его на 2, третья увеличивает на 3.
Верный ответ: 10
Все команды увеличивают число, поэтому обязательное число 13 делит программу на два независимых участка: 3 → 13 и 13 → 16. Запрещённые числа 6 и 12 учитываются на первом участке.
Для числа n последняя команда могла прийти из n − 1, из n − 3 или, если n чётно, из n / 2. Поэтому F(n)=F(n−1)+F(n−3)+F(n/2), где третье слагаемое используется только для чётных n. Для запрещённых чисел задаём F(n)=0.
Участок 3 → 13.
При F(3)=1 получаем F(4)=1, F(5)=1, F(6)=0, F(7)=1, F(8)=3, F(9)=3, F(10)=5, F(11)=8, F(12)=0, F(13)=5.
Участок 13 → 16.
При новом F(13)=1 получаем F(14)=1, F(15)=1, F(16)=2: к 16 можно прийти из 15 командой «+1» или из 13 командой «+3».
Количество полных программ равно 5 · 2 = 10.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19081.
1. Прибавить 1
2. Сделай нечётноеВыполняя первую команду, исполнитель увеличивает число на 1, а выполняя вторую – из числа x получает число 2x + 1. Сколько существует программ, для которых при исходном числе 1 результатом является число 31 и при этом траектория вычислений не содержит число 25?
Верный ответ: 44
Обозначим F(n) — число программ, переводящих 1 в n и не проходящих через 25. Последней могла быть команда «Прибавить 1», тогда предыдущее число равно n − 1. Если n нечётно, последней могла быть команда «Сделай нечётное», тогда предыдущее число равно (n − 1) / 2.
Следовательно:
• для чётного n: F(n)=F(n−1);
• для нечётного n: F(n)=F(n−1)+F((n−1)/2).
Начинаем с F(1)=1. До запрета получаем F(23)=47 и F(24)=47. Поскольку число 25 нельзя включать в траекторию, задаём F(25)=0. Тогда F(26)=0: единственный возможный предшественник 25 запрещён.
Далее команда «Сделай нечётное» позволяет снова получить допустимые значения: F(27)=F(26)+F(13)=0+13=13; F(29)=F(28)+F(14)=13+13=26; F(31)=F(30)+F(15)=26+18=44.
Такой способ автоматически исключает не только само число 25, но и все программы, которые могли бы продолжиться после прохождения через него.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19054.
1. Прибавить 1
2. Прибавить 2
3. Умножить на 3Сколько существует программ, которые преобразуют исходное число 1 в число 38, и при этом траектория вычислений содержит числа 8 и 20, но не содержит чисел 12 и 18?
Верный ответ: 1944165
Все команды увеличивают число, а траектория обязана последовательно пройти через 8 и 20. Поэтому любую программу можно единственным образом разделить на три участка: 1 → 8, 8 → 20 и 20 → 38. Запрещённые числа 12 и 18 относятся к среднему участку.
Для команд «+1», «+2», «×3» используем динамику: F(n)=F(n−1)+F(n−2), а если n делится на 3, дополнительно прибавляем F(n/3). В начале каждого участка его начальной точке присваиваем значение 1; запрещённым точкам присваиваем 0.
Участок 1 → 8: получаем 31 программу.
Участок 8 → 20 без 12 и 18: значения на запрещённых числах обнуляются; последовательный расчёт даёт F(13)=3, F(15)=6, F(17)=15, F(18)=0, F(19)=15, F(20)=15.
Участок 20 → 38: команды умножения на 3 уже не используются, потому что предшественники n/3 меньше 20. Остаётся рекурсия Фибоначчи F(n)=F(n−1)+F(n−2), дающая F(38)=4181.
Независимые варианты участков перемножаются: 31 · 15 · 4181 = 1944165.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19027.
1. Прибавь 1
2. Умножь на 2
3. Умножь на 2 и прибавь 1
Верный ответ: 229
Все команды увеличивают число. Если траектория обязана содержать 65, программу можно разделить на участки 10 → 65 и 65 → 100.
После числа 65 команды «×2» и «×2+1» дают соответственно 130 и 131, то есть сразу превышают 100. Поэтому участок 65 → 100 возможен только последовательностью из 35 команд «+1» и имеет ровно один вариант.
Остаётся посчитать программы 10 → 65. Обозначим F(n) их количество. К n можно прийти:
• из n − 1 командой «+1»;
• из n / 2 командой «×2», если n чётно;
• из (n − 1) / 2 командой «×2+1», если n нечётно.
Начинаем с F(10)=1. Последовательный расчёт даёт F(20)=2, F(30)=12, F(40)=23, F(50)=68, F(60)=163, затем F(61)=175, F(62)=188, F(63)=201, F(64)=215, F(65)=229.
Участок после 65 имеет один вариант, поэтому общее количество не изменяется: 229 · 1 = 229.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 19000.
1. Отнять 2
2. Отнять 3
3. Разделить нацело на 2Первая команда уменьшает число на экране на 2, вторая уменьшает его на 3, а третья делит нацело на 2 (например, при целочисленном делении 10 на 2 получится 5). Программа для исполнителя — это последовательность команд. Сколько существует программ, для которых при исходном числе 50 результатом является число 18, и при этом траектория вычислений содержит число 30 и не содержит число 23?
Верный ответ: 684
Все команды уменьшают число, поэтому обязательное число 30 разделяет траекторию на участки 50 → 30 и 30 → 18. Число 23 может встретиться только на втором участке.
Для убывающего исполнителя удобно считать G(n) — число программ из фиксированного начала в n, двигаясь от больших чисел к меньшим. Перед числом n могло стоять:
• n + 2, если последней была команда «Отнять 2»;
• n + 3, если последней была команда «Отнять 3»;
• 2n или 2n + 1, если последней была команда целочисленного деления на 2, потому что и 2n div 2, и (2n + 1) div 2 равны n.
Следовательно, G(n)=G(n+2)+G(n+3)+G(2n)+G(2n+1); значения выше начального числа считаются нулевыми.
Участок 50 → 30.
При G(50)=1 последовательный расчёт вниз даёт G(40)=7, G(35)=28, G(34)=37, G(33)=49, G(32)=65, G(31)=86, G(30)=114.
Участок 30 → 18 без числа 23.
Начинаем новый расчёт с G(30)=1 и задаём G(23)=0. Получаем G(24)=2, G(22)=4, G(21)=2, G(20)=4, G(19)=6, G(18)=6.
Любой путь до 30 можно соединить с любым допустимым продолжением после 30, поэтому 114 · 6 = 684.
P.S. Нашли ошибку в задании? Пожалуйста, сообщите о вашей находке ;)
При обращении указывайте id этого вопроса - 18973.