Разбор задачи «Удвоение бактерий»

1. Идея

Нужно определить, через сколько секунд количество бактерий станет не меньше m, если изначально их n, и каждую секунду число бактерий удваивается.

По условию требуется именно моделирование процесса:

• пока n < m,
• удваиваем n,
• увеличиваем число секунд на 1.

Как только n >= m, останавливаемся и выводим количество секунд.

2. Наблюдения

1. Если в самом начале n >= m, ждать не нужно, ответ равен 0.

2. За одну секунду количество бактерий меняется так:

   • было n,
   • стало 2 * n.

3. Так как n <= m, а удвоение происходит очень быстро, число шагов будет небольшим.

4. Ограничения позволяют спокойно использовать цикл while, потому что даже если n = 1, чтобы дойти до 10^9, понадобится около 30 удвоений.

3. Алгоритм

1. Считать n и m.
2. Завести переменную seconds = 0.
3. Пока n < m:
   • заменить n на n * 2,
   • увеличить seconds на 1.
4. Вывести seconds.

4. Почему это работает

Алгоритм в точности повторяет процесс из условия задачи.

На каждом шаге цикла проходит ровно одна секунда, и количество бактерий ровно удваивается. Значит:

• после 1-й итерации мы знаем число бактерий через 1 секунду,
• после 2-й итерации — через 2 секунды,
• и так далее.

Цикл заканчивается в первый момент, когда n становится не меньше m. Следовательно, значение seconds и есть минимальное число целых секунд, через которое условие выполнится.

5. Сложность

Пусть ответ равен k. Тогда цикл выполнится k раз.

• Время работы: O(k)
• Память: O(1)

Так как число удваивается, k очень мало — порядка log2(m).

6. Код на C++17

#include <iostream>
using namespace std;

int main() {
    long long n, m;
    cin >> n >> m;

    int seconds = 0;
    while (n < m) {
        n *= 2;
        seconds++;
    }

    cout << seconds << "\n";
    return 0;
}

7. Код на Python 3

n, m = map(int, input().split())

seconds = 0
while n < m:
    n *= 2
    seconds += 1

print(seconds)