Задача на Питоне Возле дома Алисы завелись ящерицы. Они в ужасе бегают по парковке и отбрасывают хвосты, а робот Локи их подбирает.
В 1-й день Локи нашёл 1 хвост, во 2-й — 3 хвоста, в 3-й — 5 хвостов, …, в k-й день он нашёл 2 * k - 1.
Есть число n. На какой день общее количество хвостов у робота впервые стало строго больше n?

Ввод Вывод
3 2
4 3

Примечание: в первый день у робота всего был 1 хвост, во второй 1 + 3 = 4 хвоста (4 больше 3), в третий 1 + 3 + 5 = 9 хвостов (9 больше 4).

Чтобы решить эту задачу, давайте разберёмся, как считать количество хвостов, которое накапливает робот Локи с каждым днём. Мы видим, что каждый день Локи находит $2 \times k - 1$ хвостов, где $k$ — это номер дня. Таким образом, количество хвостов накапливается по следующей закономерности:

1. В первый день Локи находит $1$ хвост.
2. Во второй день — $3$ хвоста.
3. В третий день — $5$ хвостов.
4. В четвёртый день — $7$ хвостов и так далее.

Эти числа $1, 3, 5, 7, ...$ представляют собой последовательность нечётных чисел, которые робот Локи собирает с каждым новым днём. Чтобы определить, когда общее количество хвостов, найденных Локи, станет строго больше числа $n$, мы можем выполнить следующий пошаговый алгоритм.

Алгоритм решения задачи:

1. Инициализируем переменные:

   • $\text{count} = 0$ — общее количество хвостов, найденных к текущему дню.
   • $k = 1$ — счётчик дней.

2. Запускаем цикл, в котором:

   • Каждый день прибавляем к $\text{count}$ количество хвостов, найденных на текущий день: $2 \times k - 1$.
   • Проверяем, если $\text{count} > n$, тогда останавливаем цикл, так как достигнуто условие задачи.
   • Если нет, увеличиваем $k$ на единицу (переходим к следующему дню).

3. Как только $\text{count} > n$, выводим $k$ — номер дня, на который это произошло.

Пример реализации на Python

python
def find_day(n):
    count = 0  # общее количество хвостов
    k = 1      # день
    
    while count <= n:
        count += 2 * k - 1  # количество хвостов, найденных в день k
        if count > n:
            return k
        k += 1

Разбор примера из задачи

Пусть $n = 3$:

1. Первый день:

   • Локи находит $1$ хвост.
   • Общее количество хвостов: $1$.
   • $1$ не больше $3$, идём дальше.

2. Второй день:

   • Локи находит $3$ хвоста.
   • Общее количество хвостов: $1 + 3 = 4$.
   • $4 > 3$, значит, ответ — $2$ (на второй день количество хвостов впервые превысило $3$).

Пусть $n = 4$:

1. Первый день:

   • Локи находит $1$ хвост.
   • Общее количество хвостов: $1$.
   • $1$ не больше $4$, идём дальше.

2. Второй день:

   • Локи находит $3$ хвоста.
   • Общее количество хвостов: $1 + 3 = 4$.
   • $4$ не больше $4$, продолжаем.

3. Третий день:

   • Локи находит $5$ хвостов.
   • Общее количество хвостов: $1 + 3 + 5 = 9$.
   • $9 > 4$, значит, ответ — $3$ (на третий день количество хвостов впервые превысило $4$).

Таким образом, функция find_day(n) будет возвращать нужный день для заданного числа $n$.