Как же скучно может быть... - вопрос №550548

Как же скучно может быть городскому жителю летом в деревне! Вот и главному герою нашей сегодняшней задачи, Егору, отправленному заботливыми родителями в деревню к дедушке и бабушке на все лето, просто невыносимо скучно. Прошел уже месяц без интернета ицивилизации, и теперь даже грядки с клубникой и соседские яблони не радуют Егора. Но сегодня Егор вот уже второй час ходит туда-сюдапо лестнице с первого этажа на второйи обратно, и, похоже, у него появилась идея, как занять себя на ближайшие несколько дней. Задача A. Дело в том, что Егор может ходить по лестнице разными шагами _ он может наступать на ближайшую ступеньку или перешагивать через ближайшую, наступая на следующую. Конечно же, в процессе подъема или спуска по лестнице он может чередовать оба вида шагов, то наступая на следующую ступеньку, то наступая на ступеньку после следующей. Такимобразом, на каждую ступеньку он может попасть множеством разных способов. Например, на ступеньку № 2 он может попасть уже двумя способами: наступить сначала на ступеньку № 1, апотом _ на ступеньку № 2, или, перешагнув через ступеньку № 1, встать сразу же на ступеньку № 2. А на ступеньку № 3 он может попасть уже тремя способами: № 1 – № 2 – № 3, № 1 – № 3, № 2 – № 3. Изначально Егор стоит перед лестницей, и ближайшей ступенькой считается ступенька № 1. ⊲ 1. Обычная лестница I. Сколькими способами он может попасть на ступеньку № 8? ⊲ 2. Лестница на крышу I. Сколькими способами он может попасть на ступеньку № 40? ⊲ 3. Лестница в стратосферу I. Сколькими способами он может попасть на ступеньку № 1000? Задача B. Ценой пары синяков и ушибов Егор научился перешагивать через две ступеньки сразу. Теперь он может за один шаг наступить на ближайшую ступеньку, или перешагнуть через одну ступеньку, или перешагнуть через две ступеньки (например, со ступеньки № 1 за один шаг он может попасть на ступеньки № 2, № 3 и № 4). (В этой и во всех последующих задачах Егор ходит по лестнице именно так.) ⊲ 4. Обычная лестница II. Сколькими способами он может попасть на ступеньку № 8? ⊲ 5. Лестница на крышу II. Сколькими способами он может попасть на ступеньку № 30? ⊲ 6. Лестница в стратосферу II. Сколькими способами он может попасть на ступеньку № 1000? Задача C. Егор слишком долго и усердно прыгал по лестнице, поэтому теперь одна из ступенек, а именно _ ступенька с номером N 3, где N _ номер ступеньки, на которую Егор пытается попасть, сломалась. Теперь вставать на эту ступеньку нельзя, однако в нумерации ступенек она все еще учитывается. Например, со ступеньки с номером N/3-1теперь можно попасть только на ступеньки N/3+1 иN/3+ 2. ⊲ 7. Обычная лестница III. Сколькими способами теперь можно попасть на ступеньку № 9? ⊲ 8. Лестница на крышу III. На ступеньку № 39? ⊲ 9. Лестница в стратосферу III. На ступеньку № 999? Задача D. Через некоторое время дедушка, ворча, починил сломанную ступеньку. Однако уже через несколько минут Егор на радостях сломал ступеньки с номерами 2, 7, 19, 20, 31, 57, 101 и 348. ⊲ 10. Обычная лестница IV. Сколькими способами теперь можно попасть на ступеньку № 9? ⊲ 11. Лестница на крышу IV. На ступеньку № 30? ⊲ 12. Лестница в стратосферу IV. На ступеньку № 2013? Задача E. Прошел час, и дедушка, теперь уже очень недовольный Егором, починил все сломанные ступеньки. Чтобы Егор больше не прыгал по лестнице, он разложил по ступенькам жгучие листья крапивы. Егор достаточно неуклюжий и давно об этом знает, поэтому ему известно, что на ступеньке с номером i он наступит на количество листьев, равное остатку от деления i на 7. Например, на первой ступеньке он наступит на 1 лист, на 10-й _ на 3 листа, а на 14-й ступеньке он сможет не наступить ни на один лист. Таким образом, теперь для того, чтобы пройти по лестнице, нужно немного пострадать. Егор хочет дойти до N-й ступеньки с минимальным количеством повреждений, то есть наступив на как можно меньшее число листьев крапивы. Например, при N =3 у него есть четыре пути: №1 – №2 – №3 травматичностью в 1+2+3=6листьев, № 1 – № 3 травматичностью в 1+3=4 листа и № 2 – № 3 травматичностью в 2+3=5листьев, либо путь, состоящий в шаге сразу на 3-ю ступеньку _ его травматичность равна 3 листьям и он, очевидно, самый безболезненный из возможных. ⊲ 13. Обычная лестница V. Найдите травматичность самого безболезненного пути на 8-ю ступеньку. ⊲ 14. Лестница на крышу V. Найдите травматичность самого безболезенного пути на 88-ю ступеньку. ⊲ 15. Лестница в стратосферу V. Найдите травматичность самого безболезненного пути на 88888-ю ступеньку. ⊲ 16. Обычная лестница V _ маршрут. Найдите самый безболезненный путь на 8-ю ступеньку. В ответе укажите через пробел в порядке возрастания номера ступенек, на которые нужно наступать, включая последнюю (например: 3 4 6 7 8). ⊲ 17. Лестница на крышу V _ маршрут. Найдите самый безболезненный путь на 88-ю ступеньку. ⊲ 18. Лестница в стратосферу V _ маршрут. Найдите самый безболезненный путь на 888-ю ступеньку. Задача F. На следующий день листья убрали, но Егору стало скучно просто так ходить полестнице. Теперь он придумал для себя следующие правила: cо ступеньки с четным номером онделает шаг на следующую ступеньку или через одну, а со ступеньки с нечетным номером _ наследующую, через одну или через две. (Первый шаг он делает по правилам четной ступеньки.) ⊲ 19. Обычная лестница VI. Сколькими способами теперь можно попасть на ступеньку № 10? ⊲ 20. Лестница в стратосферу VI. Сколькими способами теперь можно попасть на ступеньку № 1000? Задача G. Прыжки Егора по лестнице изрядно утомили его дедушку с бабушкой, поэтомутеперь дедушка собирается подняться на второй этаж, где прячется Егор, и оттаскать своегобеспечного внука за уши. Дедушка Егора делает шаг на следующую ступеньку или через одну, но один раз за весь подъем он может собраться с силами и сделать шаг через две ступеньки. Егорсмиренно ждет вполне заслуженного наказания и по привычке считает количество способов подняться на ту или иную ступеньку, теперь уже для дедушки. ⊲ 21. Обычная лестница VII. Сколькими способами дедушка может попасть на ступеньку № 9? ⊲ 22. Лестница на крышу VII. На ступеньку № 30? ⊲ 23. Лестница в стратосферу VII. На ступеньку № 2013?