Решение задачи про деление бактерий Задачу удобно решать, есл | Точка входа в программирование

Решение задачи про деление бактерий

Задачу удобно решать, если представить её как битовую маску std::uint64_t, ведь каждая бактерия удваивается в конце каждой секунды.

Рассмотрим заполнение пробирки одной бактерией. В первую секунду заполнен ровно 1 младший бит (нулевой бит) 000...0001. Через 60 секунд у нас будет заполнен 60-й бит, то есть 60-й бит является условием заполнения колбы.

Если положить три бактерии, то битовая маска примет вид 000...0011 (двоичное представление числа 3 — 11). Через 59 секунд сдвигом будет заполнен 60-й бит. Однако 59-ый бит тоже будет равен 1, и часть бактерий вывалится из пробирки.

Если рассмотреть пробирку через 58 секунд, то она не заполнится до конца, поскольку будут заняты 58-й и 59-й бит.

Ответ: 59 секунд.

Мы показали решение задачи с точки зрения программиста, но её можно решить и математически через степени двойки, что, по сути, аналогично предложенному решению.

Источник