Подтема 6 из 7 · дополнительный урок
Группы программ и обратные вопросы
Условия на несколько чисел сразу, подсчёт без таблицы и обратный вопрос: какая цель даёт нужное число программ.
Несколько чисел сразу
Дополнительный урок — для продвинутых: такие условия редки.
Сколько программ из 2 в 6 командами «+1» и «×2» проходят через 3 и 4? Через хотя бы одно из них? Через ровно одно?
Когда условие говорит о нескольких числах сразу, программы делят на группы и следят, какие из них посчитаны дважды. Из 2 в 6 ведут три программы из подтемы 1: 1111 проходит через 3 и 4, 12 — только через 3, 211 — только через 4.
И, или, ровно одно
«И» — программы через оба числа, «или» — хотя бы через одно, «ровно одно» — через одно, но не через оба.
| Условие | Программы | Всего |
|---|---|---|
| через 3 и 4 | 1111 | 1 |
| через 3 или 4 | 1111, 12, 211 | 3 |
| ровно через одно | 12, 211 | 2 |
Через 3 — две программы, через 4 — две, через оба — одна. Сумма 2 + 2 учитывает 1111 дважды, поэтому «или» — 2 + 2 − 1 = 3. Для «ровно одно» 1111 убирают из обеих групп: 2 + 2 − 2 · 1 = 2.
def f(x, y): if x > y: return 0 if x == y: return 1 return f(x + 1, y) + f(x * 2, y) a = f(2, 3) * f(3, 6)b = f(2, 4) * f(4, 6)both = f(2, 3) * f(3, 4) * f(4, 6)print(a + b - both, a + b - 2 * both)Тонкости:«или» и общий запрет
Если к «или» добавлен общий запрет — «через 6 или через 8, но не через 15», — запрет ставят в каждое из трёх слагаемых: считают через 6, через 8 и через оба с нулём в 15. Вычесть программы через 15 один раз из готовой суммы нельзя: часть из них уже учтена дважды.
Только прибавления
Команды «+1» и «+3». Сколько программ переводят 2 в 11?
Если все команды — прибавления, программу задают число команд каждого вида и их места: перебирают количества и считают расстановки. Прибавить нужно 9: если «+3» выполнено b раз, то «+1» — 9 − 3b раз.
| «+3» | «+1» | Команд | Расстановок |
|---|---|---|---|
| 0 | 9 | 9 | 1 |
| 1 | 6 | 7 | 7 |
| 2 | 3 | 5 | 10 |
| 3 | 0 | 3 | 1 |
Одну «+3» среди семи команд можно поставить на любое из 7 мест. Две «+3» среди пяти — на пару мест: 5 · 4 = 20 упорядоченных выборов, но каждая пара посчитана дважды, остаётся 10. Итого 1 + 7 + 10 + 1 = 19. Проверка таблицей K(n) = K(n − 1) + K(n − 3) от 2 до 11: 1, 1, 1, 2, 3, 4, 6, 9, 13, 19.
Тонкости:когда способ не работает
Число способов выбрать k мест из n — число сочетаний n! / (k! · (n − k)!), где n! — произведение чисел от 1 до n. Для пары мест из пяти: 5! / (2! · 3!) = 10.
Расстановки годятся, только пока порядок команд не меняет допустимость: при запрещённом числе или с умножением («+1», затем «×2» и наоборот дают разные числа) считают таблицей.
Обратный вопрос
Команды «+1» и «×2», старт 2. Какое наименьшее число получается ровно 18 программами?
В обратном вопросе таблицу считают по всему диапазону и только потом выбирают цели с нужным количеством. Нечётное число получает столько же программ, сколько предыдущее, — поэтому значения идут парами.
| n | K(n) |
|---|---|
| 12, 13 | 10 |
| 14, 15 | 13 |
| 16, 17 | 18 |
| 18, 19 | 23 |
| 20, 21 | 30 |
18 программ — у 16 и 17. Наименьшая цель — 16, а если спрашивают все цели, ответ — оба числа.
k = [0] * 22k[2] = 1for n in range(3, 22): k[n] = k[n - 1] if n % 2 == 0: k[n] += k[n // 2]print([n for n in range(2, 22) if k[n] == 18])Тонкости:останавливаться рано
С командой «+1» и без запретов количества не убывают, и первое совпадение — наименьшая цель. С запретом или без «+1» количество может упасть до нуля и снова вырасти, поэтому таблицу досчитывают до конца диапазона.
Не оба
Команды «+1» и «×2». Сколько программ из 2 в 12 не проходят через 4 и 8 одновременно?
«Не оба» — все программы минус программы через оба числа. Всего программ 10, через 4 и 8 — 2 · 2 · 1 = 4 (участки 2 → 4, 4 → 8, 8 → 12). Ответ 10 − 4 = 6.
| Условие | Как считать | Программ |
|---|---|---|
| через 4 и 8 | участки 2 → 4 → 8 → 12 | 4 |
| хотя бы через одно | 8 + 5 − 4 | 9 |
| ровно через одно | 8 + 5 − 2 · 4 | 5 |
| не через оба | 10 − 4 | 6 |
Четыре условия — четыре разные группы, и ответы у них разные. Перед счётом переведи условие в одну из этих строк.
Итого
- Ипроизведение участков через оба числа
- Илисумма групп минус пересечение
- Ровно односумма минус два пересечения
- Не обавсе минус пересечение
- Только прибавленияколичества команд и их расстановки
- Обратный вопростаблица по всему диапазону, потом выбор
Проверьте себя
Ответь сначала сам, потом открой ответ.
ОтветСкрыть ответ
ОтветСкрыть ответ
ОтветСкрыть ответ
ОтветСкрыть ответ
Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Хотя бы одно из двух
Команды «+1» и «×2», путь 2 → 6. Сколько программ проходят хотя бы через одно из чисел 3 и 4?
Введите число.
Подсказка
Сложи группы и вычти программы, посчитанные дважды.
Решение
Через 3 — две программы (1111, 12), через 4 — две (1111, 211), через оба — одна (1111): 2 + 2 − 1 = 3.
def f(x, y): if x > y: return 0 if x == y: return 1 return f(x + 1, y) + f(x * 2, y) a = f(2, 3) * f(3, 6)b = f(2, 4) * f(4, 6)both = f(2, 3) * f(3, 4) * f(4, 6)print(a + b - both)Ответ: 3
Прибавления: из 2 в 11
Команды «+1» и «+3». Сколько программ переводят 2 в 11? Реши таблицей и выбором позиций команд.
Введите число.
Подсказка
Подбери число команд «+3» и выбери для них места.
Решение
Прибавка 9 = a + 3b: b = 0 — 1 программа, b = 1 — 7 мест, b = 2 — 10 пар мест из пяти, b = 3 — 1. Итого 19.
def f(x, y): if x > y: return 0 if x == y: return 1 return f(x + 1, y) + f(x + 3, y) print(f(2, 11))Ответ: 19
Прибавления: из 1 в 15
Команды «+1» и «+3». Сколько программ переводят 1 в 15? Реши выбором мест для команд «+3» и проверь таблицей.
Введите число.
Подсказка
Прибавка 14 = a + 3b; для каждого b выбери места.
Решение
Прибавка 14 = a + 3b. При b = 0 — 1 программа, b = 1 — 12 мест, b = 2 — 45, b = 3 — 56, b = 4 — 15: всего 129. Таблица K(n) = K(n − 1) + K(n − 3) даёт то же.
def f(x, y): if x > y: return 0 if x == y: return 1 return f(x + 1, y) + f(x + 3, y) print(f(1, 15))Ответ: 129
Наименьшая цель с 20 программами
Команды «+1» и «×2», старт 1. Найди наименьшую цель, до которой ведут ровно 20 программ.
Введите число.
Подсказка
Заполни таблицу от 1 и найди первое значение 20.
Решение
Таблица от 1: 1, 2, 2, 4, 4, 6, 6, 10, 10, 14, 14, 20 — впервые 20 в 12 (и ещё в 13).
def f(x, y): if x > y: return 0 if x == y: return 1 return f(x + 1, y) + f(x * 2, y) print(min(n for n in range(1, 100) if f(1, n) == 20))Ответ: 12
Не оба сразу
Команды «+1» и «×2», путь 2 → 12. Сколько программ не проходят одновременно через 4 и 8?
Введите число.
Подсказка
«Не оба» — все программы минус программы через оба числа.
Решение
Всего программ 10, через 4 и 8 сразу — 2 · 2 · 1 = 4. Ответ 10 − 4 = 6.
def f(x, y): if x > y: return 0 if x == y: return 1 return f(x + 1, y) + f(x * 2, y) print(f(2, 12) - f(2, 4) * f(4, 8) * f(8, 12))Ответ: 6
Через 6 или 8 без 15
Команды «+1» и «×2», путь 2 → 20. Сколько программ проходят через 6 или через 8 и при этом не проходят через 15?
Введите число.
Подсказка
Запрет 15 действует на каждую группу.
Решение
С нулём в 15 на каждом участке: через 6 — 3 · 3 = 9, через 8 — 5 · 3 = 15, через 6 и 8 — 3 · 1 · 3 = 9. Ответ 9 + 15 − 9 = 15.
def f(x, y): if x == 15 or x > y: return 0 if x == y: return 1 return f(x + 1, y) + f(x * 2, y) a = f(2, 6) * f(6, 20)b = f(2, 8) * f(8, 20)both = f(2, 6) * f(6, 8) * f(8, 20)print(a + b - both)Ответ: 15