Про кузнечика задача: Практика: Динамическое программирование

Практика: Динамическое программирование

Игра с ферзём

Рассмотрим игру «Ферзя в угол» для двух игроков. В левом верхнем углу доски размером N*M находится ферзь, который может двигаться только вправо-вниз. Игроки по очереди двигают ферзя, то есть за один ход игрок может переместить ферзя либо по вертикали вниз, либо по горизонтали вправо, либо во диагонали вправо-вниз. Выигрывает игрок, который поставит ферзя в правый нижний угол. Необходимо определить, какой из игроков может выиграть в этой игре независимо от ходов другого игрока (имеет выигрышную стратегию).

Будем заполнять доску знаками «+» и «-». Знак «+» будет означать, что данная клетка является выигрышной для ходящего с неё игрока (то есть если ферзь стоит в этой клетке, то игрок, который делает ход, может всегда выиграть), а знак «-» означает, что он проигрывает. Клетки последней строки, последнего столбца и диагонали, ведущей из правого нижнего угла необходимо отметить, как «+», так как если ферзь стоит в этой клетке, то ходящий игрок может выиграть одним ходом.

Но в правом нижнем углу необходимо поставить знак «-» — если ферзь стоит в углу, то тот игрок, которых должен делать ход, уже проиграл.

Теперь рассмотрим две клетки, из которых можно пойти только в те клетки, в которых записан знак «+». В этих клетках нужно записать знак «-» — если ферзь стоит в этих клетках, то какой бы ход не сделал ходящий игрок, ферзь окажется в клетке, в которой стоит знак «+», то есть выигрывает ходящий игрок. Значит, тот, кто сейчас ходит — всегда проигрывает.

Но теперь в те клетки, из которых можно попасть в клетку, в которой стоит знак «-» за один ход, необходимо записать знак «+» — если ферзь стоит в этой клетке, то игрок, который делает ход, может выиграть, если передвинет ферзя в клетку, в которой стоит знак «-»:

Дальше таблица заполняется аналогично. В клетке ставиться знак «+», если есть ход, который ведет в клетку, в которой стоит знак «—». В клетке ставится знак «-», если все ходы из этой клетки ведут в клетки, в которых записан знак «+».

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

Упражнение №5

Реализовать алгоритм поиска выигрышных и проигрышных позиций в игре с ферзём на прямоугольном поле M на N, где N — высота, а M — ширина поля.

Упражнение №6

Реализовать алгоритм поиска выигрышных и проигрышных позиций в аналогичной игре, но ходы делает король (только вправо, вниз и по диагонали).

Динамическое программирование — базовые понятия

Динамическое программирование — базовые понятия — Tinkoff Generation

Общие принципы
Одномерная динамика: кузнечик
Двумерная динамика: черепашка
Восстановление ответа в динамике

Общие принципы

Рассмотрим такую задачу: найти N-е число Фибоначчи.

Числа Фибоначчи определяются так: $F_0 = 0, F_1 = 1, F_n = F_{n-2} + F_{n-1}$.

Эту задачу можно решить рекурсивно:

def fibonacchi(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fibonacchi(n - 2) + fibonacchi(n - 1)

print fibonacchi(20)

Однако это будет работать

очень долго.9\), потому что иначе числа получатся слишком слишком большими):

N = 200000

fib = [0] * (N + 1)
fib[1] = 1
for i in range(2, N + 1):
    fib[i] = (fib[i - 2] + fib[i - 1]) % (10 ** 9)

print fib[N]

175853125

Это и называется динамическим программированием (или динамикой, ДП). Основная идея состоит в том, чтобы * свести задачу для $N$ к задаче для чисел, меньших, чем $N$ (с помощью формулы) * хранить все ответы в массиве * заполнить начало массива вручную (для которых формула не работает) * обойти массив и заполнить ответы по формуле * вывести ответ откуда-то из этого массива

Чтобы решить задачу по динамике вы должны ответить на 5 вопросов: * Что лежит в массиве? (самый важный вопрос чаще всего) * Как инициализировать начало массива? * Как обходить массив? (чаще всего слева направо, но не всегда) * Какой формулой считать элементы массива? * Где в массиве лежит ответ?

Одномерная динамика: кузнечик

Рассмотрим такую задачу:

Есть полоска $1\times N$, кузнечик стоит на первой клетке, он может прыгать вперед на 1, 2, 3 клетки. Сколько есть способов добраться от начальной клетки до последней?

Как решать такие задачи? Нужно придумать рекуррентную формулу, как ответ для N зависит от ответа для меньших чисел.

Очень помогает посмотреть на маленькие числа (!! одна из самых важных идей для придумывания решений):

Пусть dp[x] — это количество способов добраться от 1 клетки до клетки номер x.

dp[1] = 1 способ (стоять на месте)
dp[2] = 1 способ ($1 \rightarrow 2$)
dp[3] = 2 способа ($1 \rightarrow 2 \rightarrow 3$ и $1 \rightarrow 3$)
dp[4] = 4 способа ($1 \rightarrow 2 \rightarrow 3 \rightarrow 4$ и $1 \rightarrow 3 \rightarrow 4$ и $1 \rightarrow 2 \rightarrow 4$ и $1 \rightarrow 4$)
dp[5] = 7 способов ($1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5$ и $1 \rightarrow 3 \rightarrow 4 \rightarrow 5$ и $1 \rightarrow 2 \rightarrow 4 \rightarrow 5$ и $1 \rightarrow 4 \rightarrow 5$ и $1 \rightarrow 2 \rightarrow 3 \rightarrow 5$ и $1 \rightarrow 3 \rightarrow 5$ и $1 \rightarrow 2 \rightarrow 5$)

Дальше становится сложнее. Но можно заметить закономерность. А можно и не заметить, но зато если мы сейчас придумаем формулу, мы легко проверим, работает ли она. Заодно мы получили наши значения на маленьких числах, которые нам все равно понадобится вбить в программу.

Какой последний прыжок кузнечика в его пути до N-й клетки? Один из трех вариантов: * $(N — 1) \rightarrow N$ * $(N — 2) \rightarrow N$ * $(N — 3) \rightarrow N$

То есть все пути до $N$ разбиваются на 3 группы. Причем мы знаем сколько путей в каждой группе. В первой из них ровно dp[N — 1] путей — столько путей идут до (N-1)-й клетки, и дальше идет еще один прыжок. Во второй и третьей группах поэтому тоже dp[N — 2] и dp[N-3] путей.

Так что формула получается такой: dp[N] = dp[N — 3] + dp[N — 2] + dp[N — 1].

Очень похоже на числа Фибоначчи, да? Можете посмотреть на числа, которые мы уже выписали, там все отлично подходит:

dp[4] = 4 = 1 + 1 + 2 = dp[1] + dp[2] + dp[3]

dp[5] = 7 = 1 + 2 + 4 = dp[2] + dp[3] + dp[4].

Так что программа пишется легко:

N = 20
dp = [0] * (N + 1)
dp[1] = 1
dp[2] = 1
dp[3] = 2
for i in range(4, N + 1):
    dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1]
print(dp)

[0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012]

Давайте изменим немного задачу: Теперь некоторые из клеток закрыты. То есть нам известно про конкретные клетки, что на них кузнечик прыгать не может. Тогда задача все еще решается так же, только нужно убедиться, что dp[x] = 0 для всех запрещенных x!

Также немного перепишем код, чтобы не писать отдельно случаи для 2 и 3, а также чтобы не писать в формуле сумму трех чисел (а представьте, что в задаче не 3, а 100). Будем инициализировать только dp[1]. А ко всем следующим значениям dp[i] будет прибавлять dp[i — k], где k = 1, 2, 3. Причем, если i — k < 1, то мы будем игнорировать такие клетки, и этим самым мы избавились от необходимости прописывать ответ для dp[2] и dp[3].

N = 20
BAD_CELLS = [2, 3, 6, 13]

dp = [0] * (N + 1)
is_bad = [0] * (N + 1)
for bad in BAD_CELLS:
    is_bad[bad] = 1
print(is_bad)

[0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]

if not is_bad[1]: 
    dp[1] = 1
for i in range(2, N + 1):
    if not is_bad[i]:
        for k in range(1, 4):
            if i - k >= 1:
                dp[i] += dp[i - k]
print(dp)

[0, 1, 0, 0, 1, 1, 0, 2, 3, 5, 10, 18, 33, 0, 51, 84, 135, 270, 489, 894, 1653]

Двумерная динамика: черепашка

Теперь рассмотрим такую задачу:

На каждой клетке двумерной таблички написано, сколько там лежит монет. Черепашка стоит в клетке 1×1 (верхней левой), и может двигаться только на одну клетку вниз, или на одну клетку вправо. Нужно найти максимальное число монет, которое может набрать черепашка по пути к нижней правой клетке NxM.

Первое, что приходит в голову — это просто идти черепашкой в ту клетку из соседних, где лежит больше монет. К сожалению, эта жадная стратегия не всегда работает. Например, на такой доске жадная черепашка пошла бы по следу из единичек, хотя гораздо выгоднее пойти сначала по нулям, а потом найти там большие горстки монет (40, 70, 100):

COINS = [
    [0,   1,   1,   1,   1,   1],
    [0,   0,   0,   0,   0,   1],
    [0,   40,  70,  0,   0,   1],
    [100, 0,   0,   0,   0,   1]
]
N = 4
M = 6

Тут нас снова спасает динамика. Давайте сводить задачу к предыдущей! Задачей назовем “сколько максимально монет можно набрать на пути от $0\times0$ до $i\times j$” (заменим 1-нумерацию на 0-нумерацию). Будем хранить это в двумерном массиве dp в клетке dp[i][j].

Сразу понятны некоторые свойства этого массива: * Он размера NxM * dp[0][0] = COINS[0][0] * ответ на всю задачу лежит в dp[N — 1][M — 1]

Но гораздо важнее придумать формулу для подсчета dp[i][j] через предыдущие. Легко посчитать первую строку и первый столбец: * dp[0][k] = dp[0][k — 1] + COINS[0][k] * dp[k][0] = dp[k — 1][0] + COINS[k][0]

Так как до этих клеток есть ровно один путь.

Но что делать, если есть много путей до клетки dp[i][j]? Снова разобьем их на на несколько групп в зависимости от последнего хода (! важный трюк, запомните). Последний ход был: * либо из [i][j — 1] * либо из [i — 1][j]

Поэтому формула для максимального числа монет такая: dp[i][j] = max(dp[i — 1][j], dp[i][j — 1]) + COINS[i][j].

Ну все, достаточно пройтись правильно по двумерному массиву (построчно сверху вних, а в каждой строке слева направо) и заполнить этот массив.

dp = [[None] * M for i in range(N)]

for i in range(N):
    for j in range(M):
        if i == 0 and j == 0:
            dp[0][0] = COINS[0][0]
        elif i == 0:
            dp[0][j] = dp[0][j - 1] + COINS[0][j]
        elif j == 0:
            dp[i][0] = dp[i - 1][0] + COINS[i][0]
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + COINS[i][j]
    print(dp[i])

[0, 1, 2, 3, 4, 5]
[0, 1, 2, 3, 4, 6]
[0, 41, 111, 111, 111, 112]
[100, 100, 111, 111, 111, 113]

В отличие от жадного алгоритма, динамическое программирование находит оптимальное решение — это, в данном случае, 113 монет.

Восстановление ответа

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

Есть два способа, которыми можно это сделать.

Хранить в массив prev откуда ты пришел в эту клетку.

Когда мы выбираем максимум из левой и верхней клетки, мы на самом деле решаем, какой последний ход будет в оптимальном пути до этой клетки — сверху или слева, и берем ответ для той клетки, сложнный с монетами в этой клетке. Давайте координаты клетки, откуда мы пришли, хранить в массиве prev. Или, в данном случае, можно хранить не координаты а просто 1, если пришли слева, и 0, если пришли сверху.

dp = [[None] * M for i in range(N)]
prev = [[None] * M for i in range(N)]

for i in range(N):
    for j in range(M):
        if i == 0 and j == 0:
            dp[0][0] = COINS[0][0]
            prev[0][0] = -1 # это самое начало, предыдущей клетки нет
        elif i == 0:
            dp[0][j] = dp[0][j - 1] + COINS[0][j]
            prev[0][j] = 0 # слева пришли
        elif j == 0:
            dp[i][0] = dp[i - 1][0] + COINS[i][0]
            prev[i][0] = 1 # сверху пришли
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + COINS[i][j]
            if dp[i - 1][j] > dp[i][j - 1]:
                prev[i][j] = 1
            else:
                prev[i][j] = 0
    print(prev[i])

[-1, 0, 0, 0, 0, 0]
[1, 1, 1, 1, 1, 1]
[1, 1, 0, 0, 0, 0]
[1, 0, 1, 0, 0, 1]

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

i, j = N - 1, M - 1
answer = []
answer_directions = []
while i > 0 or j > 0:
    if prev[i][j] == 1:
        i -= 1
        answer_directions.append('DOWN')
    else:
        j -= 1
        answer_directions.append('RIGHT')
    answer.append((i, j))
print answer[::-1] # reverse
print answer_directions[::-1] # reverse

[(0, 0), (0, 1), (1, 1), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5)]
['RIGHT', 'DOWN', 'DOWN', 'RIGHT', 'RIGHT', 'RIGHT', 'RIGHT', 'DOWN']

Вместо хранения массива prev догадаться по массиву dp, откуда именно черепашка пришла в эту клетку.

В данном примере это довольно легко. Если мы уже посчитали весь массив dp, то теперь можно начиная с конца легко понять, пришла черепашка туда сверху или слева в оптимальном маршруте — она пришла из клетки с максимальным числом монет.

i, j = N - 1, M - 1
answer = []
answer_directions = []
while i > 0 or j > 0:
    if i != 0 and (j == 0 or dp[i - 1][j] > dp[i][j - 1]):
        i -= 1
        answer_directions.append('DOWN')
    else:
        j -= 1
        answer_directions.append('RIGHT')
    answer.append((i, j))
print answer[::-1] # reverse
print answer_directions[::-1] # reverse

[(0, 0), (0, 1), (1, 1), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5)]
['RIGHT', 'DOWN', 'DOWN', 'RIGHT', 'RIGHT', 'RIGHT', 'RIGHT', 'DOWN']

Задание

Решите как можно больше задач из простого контеста:

https://informatics.msk.ru/mod/statements/view.php?id=33233#1

А также решите как можно больше задач из сложного контеста:

https://informatics.msk.ru/mod/statements/view.php?id=35808#1

Разбор еще нескольких задач

Давайте разберем еще несколько задач.

Последовательности без 3 единиц подряд

Условие:

Определите количество последовательностей из нулей и единиц длины $N$, в которых никакие три единицы не стоят рядом.

Решение:

Давайте хранить в $dp[N]$ ровно число таких последовательностей длины $N$ (это первое, что должно приходить в голову).

Давайте посмотрим для начала для маленьких чисел:

$dp[0] = 1 (\text{пустая последовательность})$
$dp[1] = 2 (0, 1)$
$dp[2] = 4 (00, 01, 10, 11)$
$dp[3] = 7 (000, 001, 010, 011, 100, 101, 110)$
$dp[4] = 13 (0000, 0001, 0010, 0011, 0100, 0101, 0110, 1000, 1001, 1010, 1011, 1100, 1101)$

Сходу закономерность можно не увидеть. Нужно догадаться сгруппировать эти числа по том, сколько в конце единичек. Например, для dp[4]:

0 единичек в конце: $0000, 0010, 0100, 0110, 1000, 1010, 1100$ — их ровно семь, как для $N=3$, потому что первые 3 числа могут быть любые (но без трех единиц подряд), а четвертое — 0
1 единичка в конце: $0001, 0101, 1001, 1101$ — их ровно четыре, как для $N=2$, потому что первые 2 числа могут быть любые (но без 3 единиц подряд), а два последних — 01
2 единички в конце: $0011, 1011$ — их ровно две, как для $N=1$, потому что первое число может быть любым (но без 3 единиц подряд), а три последних — 011

Так мы замечаем и доказываем формулу: $dp[N] = dp[N-1] + dp[N-2] + dp[N-3]$

Теперь за $O(N)$ ее легко посчитать.

Лесенки

Условие:

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

■	■
■	■	■
■	■	■	■	■
■	■	■	■	■	■	■	■

Решение:

Если считать, что $dp[N]$ — это число лесенок из $N$ кубиков, то никакой закономерности скорее всего найти не получится.

По числам построить закономерность сложно, и по самим лесенкам тоже. Не видно какого-то рассуждения вида “ко всем лесенкам размера N-1 можно положить на любой слой еще один кубик”, иногда ведь и нельзя.

Тут нам помогает введение дополнительного параметра. Нас просят решить одномерную задачу (для $N$), а мы решим двумерную задачу для $n$ и $m$. Давайте зафиксируем размер самого нижнего слоя и назовем его размер $m$.

То есть $dp[n][m] = $“число лесенок, состоящих из $N$ кубиков, таких, что самый нижний слой состоит из $M$ кубиков”.

Как это связано с нашей задачей? Ответ на нашу задачу равен $dp[N][1] + dp[N][2] + \ldots + dp[N][N]$.

Какая есть формула для такой постановки задачи? Размер нижнего слоя у нас зафиксирован и равен $m$, осталость $n-m$ кубиков на верхних слоях. Логично перебрать размер второго снизу слоя, который может быть любым от $1$ до $m-1$: $dp[n][m] = dp[n-m][1] + dp[n-m][2] + \ldots + dp[n-m][m-1]$

Это все пир условии, что $n \geq m$. Иначе $dp[n][m] = 0$.

Теперь осталось понять как инициализировать этот массив и аккуратно по нему пройтись. Давайте инициализируем его ровно для случая $n=0, m=0$:

$dp[0][0]$ = 1

Пройдемся по массиву сначала для всех m при n = 1, потому для всех m при всех n = 2 и так далее — то есть по строчкам обычными двумя циклами $for$.3)\).

Занятие 6. Исполнитель Кузнечик — Программирование в системе Кумир

Цели. Познакомиться с исполнителем Кузнечик, с его операторами. Решение задач на исполнителе Кузнечик. Создание задач на исполнителе Кузнечик.

Для знакомства с исполнителем Кузнечик из главного окна КуМира вызовите описание командами

Инфо → Описание миров → Кузнечик.

Из окна Кузнечика из меню Задания задайте длины прыжков, начальное положение, область, доступную Кузнечику, флаги.

С помощью пульта произвольно выполните управление Кузнечиком, используйте прыжки, закрашивание и стирание координат.

Задание 1

Откройте окно исполнителя Кузнечик.

Установите задания: прыжок вперёд (вправо) на 2, прыжок назад (влево) на 1, начальное положение в 0, область от -10 до 10.

Откройте пульт для исполнителя Кузнечик.

Используя пульт, напишите алгоритм для закрашивания всех нечётных координат. Составьте программу, используя оператор цикла.

Вариант решения.

использовать Кузнечик

алг

нач

нц 5 раз

вперед 2

кц

назад 1

перекрасить

нц 9 раз

назад 1

перекрасить

кц

кон

Задание 2.

Откройте окно исполнителя Кузнечик

задании Установите задания так, что Кузнечик умеет выполнять команды «вперед 3», «назад 4», начальное положение в 33. Используя команды исполнителя Кузнечик, напишите алгоритм для получения из числа 33 числа 4 (без использования пульта).

Задание 3.

Исполнитель КУЗНЕЧИК живёт на числовой оси. Начальное положение КУЗНЕЧИКА – точка 0. Система команд Кузнечика:

Вперед 4, Назад 3.

Какое наименьшее количество раз должна встретиться в программе команда «Назад 3», чтобы Кузнечик оказался в точке 27? Составьте программу.

Задание 4.

Вперед 3, Назад 4.

Какое наименьшее количество раз должна встретиться в программе команда «Назад 4», чтобы Кузнечик оказался в точке 31? Составьте программу.

Задание 5.

Переместить Кузнечика из точки 0 в точку 10, в точки с флажками не заходить, закрасить точку 10.

Условия: исходная позиция – точка 0; Вперед 3, Назад 2, Флажки – в точках 3, 7.

Задание 6. Составьте интересное на Ваш взгляд задание для Кузнечика, которое имеет небольшое количество решений.

Задание № 20. Задачи на логику и смекалку (кузнечик, улитка)

Задание № 20. Задачи на логику и смекалку

Тип №1 (про кузнечика)

1. Кузнечик прыгает вдоль координатной прямой в любом направлении на единичный отрезок за один прыжок. Сколько существует различных точек на координатной прямой, в которых кузнечик может оказаться, сделав ровно 11 прыжков, начиная прыгать из начала координат.

Решение.

Заметим, что кузнечик может оказаться только в точках с нечётными координатами, т.к. количество прыжков, которое он делает, — нечётно. Максимально кузнечик может оказаться в точках, модуль которых не превышает одиннадцати. Таким образом, кузнечик может оказаться в точках: −11, −9, −7, −5, −3, −1, 1, 3, 5, 7, 9 и 11; всего 12 точек.

Ответ: 12.

2. Кузнечик прыгает вдоль координатной прямой в любом направлении на единичный отрезок за прыжок. Сколько существует различных точек на координатной прямой, в которых кузнечик может оказаться, сделав ровно 6 прыжков, начиная прыгать из начала координат?

Решение.

Заметим, что кузнечик может оказаться только в точках с чётными координатами, поскольку число прыжков, которое он делает, — чётно. Максимально кузнечик может оказаться в точках, модуль которых не превышает шести. Таким образом, кузнечик может оказаться в точках: −6, −4, −2, 0, 2, 4 и 6; всего 7 точек.

Ответ: 7.

Вывод. Из решения представленных задач видно, что количество различных точек на координатной прямой, в которых кузнечик может оказаться, на 1 больше числа совершённых им прыжков.

Задания для самостоятельного решения

1. Кузнечик прыгает вдоль координатной прямой в любом направлении на единичный отрезок за один прыжок. Сколько существует различных точек на координатной прямой, в которых кузнечик может оказаться, сделав ровно 8 прыжков, начиная прыгать из начала координат.

2. Кузнечик прыгает вдоль координатной прямой в любом направлении на единичный отрезок за один прыжок. Сколько существует различных точек на координатной прямой, в которых кузнечик может оказаться, сделав ровно 9 прыжков, начиная прыгать из начала координат.

Тип № 2 (про улитку)

1. Улитка за день заползает вверх по дереву на 4 м, а за ночь сползает на 3 м. Высота дерева 10 м. За сколько дней улитка впервые доползёт до вершины дерева?

Решение.

За день улитка заползёт на 4 метра, а за ночь — сползёт на 3 метра. Итого за сутки она заползёт на метр.

За шестеро суток она поднимется на высоту шести метров. И днём следующего дня она уже окажется на вершине дерева.

Ответ: 7.

2. Улитка за день заползает вверх по дереву на 4 м, а за ночь сползает на 2 м. Высота дерева 12 м. За сколько дней улитка впервые доползёт до вершины дерева?

Решение.

За день улитка заползёт на 4 метра, а за ночь — сползёт на 2 метра. Итого за сутки она заползёт на 2 метра.

За четверо суток она поднимется на высоту восьми метров. И днём следующего дня она уже окажется на вершине дерева.

Ответ: 5.

Примечание. Можно рассуждать так: В последний день улитка может подняться вверх на 4 метра. Значит, 12 – 4 = 8 (м) надо преодолеть за предыдущие дни. Так как за сутки улитка заползёт на 2 метра, то 8 : 2 = 4 (дня) ей понадобится, чтобы подняться на 8 метров. Следовательно, всего 1 + 4 = 5 дней.

Задания для самостоятельного решения

1. Улитка за день заползает вверх по дереву на 4 м, а за ночь сползает на 1 м. Высота дерева 13 м. За сколько дней улитка впервые доползёт до вершины дерева?

2. Улитка за день заползает вверх по дереву на 4 м, а за ночь сползает на 2 м. Высота дерева 14 м. За сколько дней улитка впервые доползёт до вершины дерева?

3. Улитка за день заползает вверх по дереву на 2 м, а за ночь сползает на 1 м. Высота дерева 11 м. За сколько дней улитка доползёт от основания до вершины дерева?