Хочу разобраться с условием задачи

Дали следующую задачу (полное условие) - "На вершине лесенки, содержащей N ступенек, находится мячик, который начинает прыгать по ним вниз, к основанию. Сначала мячик может прыгнуть максимум на N/2, но с каждым ударом о ступеньку эта величина сокращается вдвое пока он не начинает катиться, перекатываясь с одной ступеньке на другую. Так мячик может прокатиться еще N/16 ступенек. Определите число всевозможных "маршрутов" мячика и найдите максимально возможную длину лестницы N."

Собственно - я бы и сам написал программу на Python, но не могу понять условие.

- Если мячик может прыгнуть на N/2, а в конце еще и на N/16 ступенек - то что делать если ступенек, например, пять? В начале он может прыгнуть на 2,5 ступеньки? Нужно округлять вверх, вниз, или вообще, брать число ступенек, делящееся на 16?
- Что значит "эта величина сокращается"? Та, которая N/2, или та, которую выбрал мячик? Например, на лестнице было 16 ступенек. Мячик мог прыгнуть максимум на 8, но, допустим, прыгнул меньше - на 4. В следующий раз он может прыгнуть на N/2 - это максимум на 8/2 = 4 ступени, или на 4/2 = 2 ступени?
- Что значит максимальная длина лестницы? По идее, она же может быть любая? Ну, например, 2^20. Вначале мячик может прыгнуть на максимум 2^19, и там же (на ступени 2^19) окажется. Затем он прыгнет на N/4 - на 2^18, и окажется на ступени 2^18, затем прыгнет на N/8 - на 2^17 ступеней, и окажется на ступени 2^17. Что делать потом
- Вариант 1: Судя по условию - величина сокращается вдвое пока он не начинает катиться с одной ступеньки на другую - получается 2^17 --> 2^16 --> 2^15 -->... 2? Но тогда в любом случае в итоге он сможет перекатываться еще N/16 ступенек, что явно больше двух. Получается он всегда сможет скатиться?
- Вариант 2: Или мячик всегда катится максимум на N/2 --> N/4 --> N/8 --> N/16, и все? Но тогда зачем в условии указано что "пока он не начинает катиться"?

В общем полные непонятки с этой задачей. Как вообще ее можно "математизировать"? Если кто-то понял условие - можете если не привести программу подсчета на Python (тут согласен, я сам должен попытаться), то хотя бы показать на небольшом N - какие есть варианты "маршрутов", и подсчитать их количество?

0

Странная задача, берем допустим лестницу на 12 ступеней, по условию после падения инерции, мяч катится на 12 / 16, это как?

Добавлено через 5 минут
Тут бы был простой ДП, если бы не этот момент, ну вот пример:

1. Прыгаем на 12 / 2 == 6.
2. Оказываемся на 6 ступени.
3. Прыгаем на 6 / 2 == 3
4. Оказываемся на 3 ступени.
5. Прыгаем на 3 / 2 == 1 (с окр вниз, так как условие не дальше n / 2)
6. Оказываемся на 2 ступени.
7. По идее начинаем катиться, но катиться дальше не можем, не позволяется остаток ибо 12 / 16 меньше 1.

Вывод, остаемся там лежать и глядеть в небо.
И это маршрут с максимальным начальным прыжком.

0

Просто тогда получается что даже при N=3 мы остаемся лежать и смотреть в небо. Вначале мы можем прыгнуть на 3/2 = 1 (с округлением вниз) - на вторую ступень. А дальше опять лежим? То есть даже при N=3 задача уже не решаема в том смысле, что мячик вниз не упадет. Что тогда подразумевают под "максимальным значением N" непонятно.

0

Ну почему не решаемая, просто маршрутов в этом случае будет ноль. Если в рамках задачи такое приемлемо, тогда все просто.

0

Я имею в виду - что написано "Найдите максимальное N". Как я понимаю, максимальное - в том смысле, что максимальное N, когда маршруты еще есть? Но вот при N=3 маршрутов уже НЕТ.

0

Но уточнять все равно нужно, дело в N / 16, ладно для малых чисел, а для например 16 000, может на 1 000 катиться для достижения цели? В этом случае выглядит странно, мяч потерял инерцию на 13 шаге, но катится дальше на 1000 ступеней .
Если это условие верно, тогда маршруты вычисляются достаточно просто.

0

Хорошо, допустим, у нас 12 ступеней. Первым шагом мы можем прыгнуть на ступень 11, 10, 9, 8, 7 или 6. Допустим, мы прыгнули на ступень №8. Следующий прыжок может быть на сколько ступеней? На 3, потому что первый максимум был на 6, а теперь вдвое меньше, или на 2, потому что хоть мячик мог прыгнуть на 6 ступеней, но прыгнул-то на 4, значит теперь его максимальная скорость равна 4/2 = 2?

0

А вот на счет максимальной лестницы, тут конечно загнули, любое число через деление нацело на 2 можно привести к единице. Потери на делении будут точно компенсированы условием про то, что мячик может дальше катиться, следовательно вывод, лестница имеет максимальный размер равный бесконечности.

Например для 10 ** 100 останется прокатиться всего 105 ступеней, что очевидно меньше, чем 10 ** 100 / 16

Добавлено через 5 минут
blueboar2, смотри, еще раз:

1. Длина прыжка определяется только 1 раз, в самом начале.
2. Она не может быть больше, чем длина лестницы // 2.
3. Каждый прыжок уменьшает расстояние в 2 раза, примеры 16 - 8 - 4 - 2 - 1, 16 - 4 - 2 - 1, 16 - 6 - 3 - 1
4. Если текущее значение прыжка равно единицы, считается, что мяч начал катиться.
5. Прокатиться он может не больше, и вот тут вопрос, чем начальная высота / 16 или же высота последнего прыжка / 16...или еще что-то

0

Два вопроса:
1) 16 - 4 - 2 - 1 - это как? Он сразу же первым прыжком прыгнул на 12 единиц? Максимум же 16//2 = 8?

2) Если все так - то получается число способов сразу же равно N/2? Именно столько начальных скоростей, а дальше они просто падают вдвое, но количество способов от этого не меняется же? Или количество зависит от количества "перекатываний" в конце? Но там тоже все просто - оно может проходить N//16 способами?

Добавлено через 11 минут
Прокатиться не больше чем начальная высота // 16 по идее, они же обозначены буквами N в условии. Если допустим N=32, то не более двух раз (один или два, ноль быть не может, потому что хотя бы один раз он прокатится путем деления скоростей). Получаем варианты (по два в каждой строке):

1) 32 --> 31 ( и возможно --> 30)
2) 32 --> 30 --> 29 (и возможно --> 28)
3) 32 --> 29 --> 28 (и возможно --> 27)
4) 32 --> 28 --> 26 --> 25 (и возможно --> 24)
5) 32 --> 27 --> 25 --> 24 (и возможно --> 23)
6) 32 --> 26 --> 23 --> 22 (и возможно --> 21)
7) 32 --> 25 --> 22 --> 21 (и возможно --> 20)
8) 32 --> 24 --> 20 --> 18 --> 17 (и возможно --> 16)
9) 32 --> 23 --> 19 --> 17 --> 16 (и возможно --> 15)
10) 32 --> 22 --> 17 --> 15 --> 14 (и возможно --> 13)
11) 32 --> 21 --> 16 --> 14 --> 13 (и возможно --> 12)
12) 32 --> 20 --> 14 --> 11 --> 10 (и возможно --> 9)
13) 32 --> 19 --> 13 --> 10 --> 9 (и возможно --> 8)
14) 32 --> 18 --> 11 --> 8 --> 7 (и возможно --> 6)
15) 32 --> 17 --> 10 --> 7 --> 6 (и возможно --> 5)
16) 32 --> 16 --> 8 --> 4 --> 2 --> 1 (и возможно --> 0)

0

А может, мячик на каждом шаге может прыгнуть на любую величину не больше, чем половина предыдущего прыжка.

Например, первый прыжок на 16 ступенек, но второй не обязательно на 8 ступенек, может и на 6 или 7 ступенек, а третий на 2 или 3 ступеньки допустим.

Добавлено через 2 минуты
Откуда эта задача? Можно ссылку на источник?

0

Получаем что нужно просто рассмотреть все N/2 случаев - и посмотреть для каждого из них - сколько вариантов дает перекатывание (оно может быть меньше чем N/16 случаев - потому что в крайних из них он тогда сможет укатиться ниже первой ступеньки)?

Добавлено через 3 минуты
К сожалению первоисточника нет, эту задачу просто задали решить. Но я нашел - что ее уже задавали на нашем форуме - то есть, не я один с ней столкнулся (правда ответа там нет) - Определите число всевозможных "маршрутов" мячика и найдите максимально возможную длину лестницы N

0

Сообщение от blueboar2 эту задачу просто задали решить.

То есть вы не просто нашли на каком-то сайте эту задачу, а существует конкретный человек, задавший вам эту задачу. Вот и адресуйте ему ваши вопросы.

0

Я так и сделаю. Просто думал - что если она есть в Интернете - значит задача известная, и кто-то уже знает, как ее понимать.

0

blueboar2, я примеры показал, какие могут быть прыжки с точки 16 - 4 первый - 2 второй - 1 третий. В общем верно уже сказали выше, задай ка вопросы автору (или преподавателю), дальше все просто.

Почему то мне кажется, что это какая-то самодельная интерпретация по аналогии задач с Трибоначчи.

0